3 ms·
A kd-tree is the generalized data structure that can do log(n) lookups of nearest in any dimensions. I wrote an implementation for nearest to a geographical poi
by AnotherGoodName 6y ago
A kd-tree is the generalized data structure that can do log(n) lookups of nearest in any dimensions. I wrote an implementation for nearest to a geographical point years ago (since ported to many other languages): https://github.com/AReallyGoodName/OfflineReverseGeocode https://github.com/AReallyGoodName/OfflineReverseGeocode
A less generalized solution is to grid things up (quad tree and oct trees) as you implied above but the kd-tree is the generalized solution without edge cases (what if the majority of points of interest end up in a single grid square in your example?). A kd-tree is essentially what a sort list is for one dimensional data but instead supports multiple dimensions.
- PartiallyTyped 6y ago> what if the majority of points of interest end up in single grid square in your example? Geohash provides arbitrary precision, at 8 character length, we can measure difference in in the order of decameters iirc. The edge cases are on the literal edges, where you could have two points, one at say -79.995, 35.0 and -80.001, 35.0, so the area is split at -80 and the first point has different prefix than the second even though they are very very close.
- claytongulick 6y agoI did some pretty effective geospatial clustering with quad trees. Had to do some smoke and mirrors to take the grid out of it, but worked great overall.