5 ms·
> Manhattan distance approximation is seriously wrong The Manhattan (1-norm) metric is strongly equivalent to euclidean (2-norm) metric. Depending on your pro
by pdpi 11y ago
> Manhattan distance approximation is seriously wrong
The Manhattan (1-norm) metric is strongly equivalent to euclidean (2-norm) metric. Depending on your problem domain, that might be good enough.
- mikeash 11y agoWhen the goal is to find the closest point out of a set of points, it's pretty wrong. This is especially true when you consider that it's doing Manhattan distance on raw latitude and longitude. That means that if you happen to be near the poles, you could end up choosing a point that's orders of magnitude farther away than the nearest point. Even in more usual latitudes it means you'll treat east-west distances as substantially longer than north-south distances. Sure, it could be a reasonable choice for some problems, but I have a hard time thinking of which ones those would be, and it would definitely need some discussion about the tradeoffs.
- pdpi 11y agoLike I said, "depending on the problem domain". In something close enough to a plane, you're guaranteed to be no worse than ~1.4 times the optimal solution. In an urban setting, euclidean tends to underestimate walking distance, so manhattan would compare even better. If you're working at close to fixed latitude, you can squash longitudes by a fixed amount and that'll give you a decent correction factor. Of course, this is true iff speed matters more than accuracy, and the relevant assumptions hold. I'm sad, though, that he didn't just try to convert the original sophisticated function to numpy. I suspect the end result would've been "the really accurate function actually performs decently!"
- mikeash 11y agoI'm talking about this specific case, not the entire generalized idea of applying Manhattan distance to anything. Yeah, on a plane you're off by at most 1.4, but this isn't on a plane. And really, I have no objection at all to approximations, but the lack of any acknowledgement that it even was an approximation is what bugged me.
- pdpi 11y agoFair deuce, the lack of acknowledgement does bug me as well.
- jfpuget 11y agoYou should reread the post to find the acknowledgement that was there since the begining: ' ignoring the fact that 1 degree difference in latitude yields a larger distance than 1 degree difference in longitude'
- mikeash 11y agoTrue, but then it's never mentioned again even though the results could end up being way off, and there's more potential for error than the longitude factor that isn't mentioned at all.
- jfpuget 11y agoRaw longitude is by far the largest approximation. It becomes really flawed near poles. But all my points are in mainland USA, and there we're pretty safe. Anyway, I did say that I was using an approximation.