News for hackers. Stuff that matters.
Re:A dive into spatial search algorithms by geophile on Friday April 28, 2017 @01:56PM (#14221598)
This discussion is incomplete without mentioning space-filling curves. These curves map the data into a 1-d space and then you can use any conventional search structure -- sorted array with binary search, balanced tree, skiplist, b-tree, etc. This allows you great flexibility, including the use of 3rd party libraries of data structures.

(A quadtree is basically the z-order space-filling curve combined with a trie of degree 4. Octtree -- degree 8.)

This approach also handles non-point data very cleanly. A non-point object gives rise to multiple index entries. (You can tune the number of index entries quite easily.)

Space-filling curves also leads to a very nice kNN algorithm: To find the k nearest neighbors of p, first search the index for p. Find k neighbors along the space-filling curve, (these are adjacent in the index), and of these, pick the point q maximizing distance(p, q). All k nearest neighbors of p must be in a circle centered at p with radius distance(p, q). Now search your index again using this circle and pick the k points n1, ..., nk minimizing distance(p, ni).

Re:A dive into spatial search algorithms by robrenaud on Friday April 28, 2017 @03:56PM (#14222584)
Yeah, the effectiveness of that idea mad me a little sad when I worked on google maps. I spent all this time studying computational geometry in college and it went out the window. Use space filling curves and then standard text indexing techniques and you don't need to deal with any fancy geometric algorithms.
Re:A dive into spatial search algorithms by amelius on Friday April 28, 2017 @05:09PM (#14223065)
Space filling curves, although elegant, are not a solution for every problem in computational geometry of course.
Re:A dive into spatial search algorithms by bane on Friday April 28, 2017 @08:35PM (#14224289)
I'd really enjoy reading anything you're aware of on this topic.
Re:A dive into spatial search algorithms by tps5 on Friday April 28, 2017 @06:00PM (#14223466)
Do you have any references to recommend on this subject?
Re:A dive into spatial search algorithms by geophile on Friday April 28, 2017 @08:31PM (#14224278)
I've been out of it for a while, but the wikipedia page on z-order is probably a good place to start. https://en.wikipedia.org/wiki/Z-order_curve. This discusses the basic idea of using a space-filling curve to map data to 1-d, and then using a conventional search structure. Hilbert curves should preserve proximity better.

Sorry to toot my own horn, but I wrote some papers that should be useful to someone learning the topic:

1) Algorithms based on space-filling curves for spatial join, a generalization of range search, points in a polygon, etc.: Orenstein & Manola, IEEE Transactions on Software Engineering, Volume 14.

2) How to tune the index for non-point spatial objects: Orenstein, ACM SIGMOD 1989.

You might also find my software, which implements these ideas, useful: https://github.com/geophile

There have been many papers elaborating on the idea, but I haven't kept up with the area. Given that you can get such good results using space-filling curves and standard data structures, I think it's nuts to do anything else. I mean look at Postgres and MySQL. The spatial indexes in these systems have never been fully integrated because they are distinct index structures, always lagging behind progress with the main index structures.

Re:A dive into spatial search algorithms by anarazel on Friday April 28, 2017 @09:53PM (#14224583)
In postgres not much has happened around geospatial in core, because there's a lot happening in postgis.

FWIW, you can define additional types of index access methods in postgres (from scratch), or you can gist / gin / spgist access methods where you need to care about a lot less. All are used in the wild.