4 ms·

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 s

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).

robrenaud 10y ago
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.
- amelius 10y ago
  Space filling curves, although elegant, are not a solution for every problem in computational geometry of course.
- bane 10y ago
  I'd really enjoy reading anything you're aware of on this topic.
tps5 10y ago
Do you have any references to recommend on this subject?
- geophile 10y ago
  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 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 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.
  - anarazel 10y ago
    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.

robrenaud 10y ago

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.

amelius 10y ago
Space filling curves, although elegant, are not a solution for every problem in computational geometry of course.
bane 10y ago
I'd really enjoy reading anything you're aware of on this topic.

tps5 10y ago

Do you have any references to recommend on this subject?

geophile 10y ago
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 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 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.
- anarazel 10y ago
  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.