Spatial Indexing Techniques

Sounds like an R* tree or some variant of that?

Another suggestion. Implement the R-tree.

There has been a lot of work in this area. There is no best algorithm, it depends upon the problem that you are trying to solve. However, I think that r-trees have advantages over k-d trees for this 2d case. Alternatively, there are Quadtrees which have different trade-offs to r-trees. A very different approach is to use space-filling curves to reduce the 2d problem to a 1d problem; this approach is normally called geohashing. If you search on these terms then you can rapidly find resources and

Add geospatial to your comparison chart please. The way in which these implement support varies widely in performance and accuracy. I've yet to find one that actually uses R-Trees. Geohashes seem to be all the rage these days.

Ever heard of geospatial hierarchical Indices?E.g. Uber's H3 index or Google's S2 index.

For reference: The generic name what op does is "spatial indexing". There is an algorithm for efficiently working with such data called Hilbert R-tree (https://en.wikipedia.org/wiki/Hilbert_R-tree). But there are alternatives (see https://en.wikipedia.org/wiki/

A deep dive into how to choose the right polygon for spatial indexing and why hexabins might be a better choice than Geohashes in some cases.

This is called a quadtree. Here's a comparison: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...

Wow, spatial indexing day on HN.Why not use a space-filling curve, and any convenient 1-d search structure that parallelizes easily?

Like to see comparison to when they use a spatial index like strtree or rtree.