Hacker News Reader

Comment by cwmma | Hacker News Reader

so it looks like your doing a geohash for the geoindexing bure not using a hilbert curve[1]? Did you guys look into more flexible structures like an rtree or some of the other stuff from libspatialindex [2] which might be a bit more flexible (e.g. for finding what polygon a point is in)

[1]http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...

[2]http://libspatialindex.github.io/

View on HN

Hi cwmma. RethinkDB actually does use Hilbert curves at multiple scales for indexing geometry. The implementation for this mapping comes from Google's S2 library. You can find the details documented in Google's code: https://code.google.com/p/s2-geometry-library/source/browse/...

We looked into some other data structures before settling for our current approach. Using a space-filling curve turned out to be the least error-prone to implement given that we already have a highly optimized and well tested btree implementation in RethinkDB.

yeah my bad I was looking through the wrong source. Do you do anything special for point queries, e.g. what town is this point in, which geohashes tend not to be that great for (in my experience)

Nothing special. We use S2 to compute a covering of a polygon (like a town) by a number of grid cells. If you insert a polygon (or line) into a geospatial index, it will actually be inserted multiple times, with one entry for each grid cell of its covering. Then when you query by a point (e.g. to answer said query, assuming you have a table with all the town polygons), we find any polygon that has a grid cell that intersects with that point and then do a post-filtering check using the actual detailed geometry of the candidate polygon. This is fairly efficient and can be extended to a lot of different cases, though I'm sure there are more efficient specialized data structures for some specific types of queries.

Reply on news.ycombinator.com