3 ms·

What are the general solutions to handling spatial data and in particular, 'nearness' in huge databases? Last time I needed something along those lines, I impl

What are the general solutions to handling spatial data and in particular, 'nearness' in huge databases? Last time I needed something along those lines, I implemented geohash [1] in the application level ontop of a time-series database. I assume there is a better, more sound way to achieve that, as geohash doesn't handle boundaries well. --- For the uninitiated, geo-hash uses a space filling curve multiple times at different precision to map quadrants into strings. So imagine a map, top left is North America, bottom right Australia, we can name the quadrants 0,1,2,3, we then take each quadrant and again use a z filling curve to split it to more quadrants (well, quadrant of a quadrant) and keep the name we gave it, we repreat the process up to desired precision, finally, we take the all the names of quadrants with the same order and concatenate them, to create a string that repretents the position. Strings with the same prefix are in the same quadrant and depending on the length of the prefix, the quadrant they are in is either bigger or smaller, longer prefix, smaller quadrant. We found that geohash, even at the application level, provided much faster queries than searching for coordinates within range on two fields. --- [1] https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash

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 ago
  I 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.
durkie 6y ago
Spatialite has some nice spatial indexing features built in that work very well. This is an older article series that talks about Spatialite spatial indexes, but most of the queries in it still work today: https://northredoubt.com/n/2012/01/18/spatialite-and-spatial-indexes/ https://northredoubt.com/n/2012/01/18/spatialite-and-spatial...
mro_name 6y ago
I recently ported the wonderful geohash computation approach of https://mmcloughlin.com/posts/geohash-assembly https://mmcloughlin.com/posts/geohash-assembly into an OCaml CGI conversion webservice. There are so many subtle gems in that article, a pleasure to read. The bit-fiddling reminded me of invsqrt.

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 ago
I 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.

durkie 6y ago

Spatialite has some nice spatial indexing features built in that work very well. This is an older article series that talks about Spatialite spatial indexes, but most of the queries in it still work today: https://northredoubt.com/n/2012/01/18/spatialite-and-spatial-indexes/ https://northredoubt.com/n/2012/01/18/spatialite-and-spatial...

mro_name 6y ago

I recently ported the wonderful geohash computation approach of https://mmcloughlin.com/posts/geohash-assembly https://mmcloughlin.com/posts/geohash-assembly into an OCaml CGI conversion webservice. There are so many subtle gems in that article, a pleasure to read. The bit-fiddling reminded me of invsqrt.