4 ms·

Agreed re: the quality of Frank McSherry's posts - they're all great fun and push the technical envelope! I'm glad you brought up Hilbert ordering. It's fascin

by Smerity 11y ago

Agreed re: the quality of Frank McSherry's posts - they're all great fun and push the technical envelope! I'm glad you brought up Hilbert ordering. It's fascinating but I rarely see it. I usually see Z-order curves in their place - simpler and more intuitive but also less effective. Does anyone know of large scale databases with Hilbert ordering out of the box? For anyone who hasn't seen them before, or why they help in ordering, I highly recommend "Portrait of the Hilbert curve"[1] and "Spatial indexing with Quadtrees and Hilbert Curves"[2]. The tldr is that they enable efficient multi-dimensional indexing. Given a request like "X < 40 and Y > 80", most databases need to run "X < 40" and then filter over the results for "Y > 80" - Hilbert curves allow you to find the query's intersection and only then perform minor filtering. As far as large scale use of Hilbert ordering, Google use it internally for much of their geographical work. They even open sourced a Java library specialised in multi-dimensional indexing based on Hilbert curves called Uzaygezen[3]. [1]: http://corte.si/%2Fposts/code/hilbert/portrait/index.html http://corte.si/%2Fposts/code/hilbert/portrait/index.html [2]: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-... [3]: http://google-opensource.blogspot.com/2008/08/uzaygezen-multi-dimensional-indexing.html http://google-opensource.blogspot.com/2008/08/uzaygezen-mult...

jandrewrogers 11y ago
The primary advantage of Hilbert curves relative to Morton (Z) curves is that they are marginally more efficient at linearizing multidimensional point indexes e.g. storing on spinning disk. However, the reason that Hilbert curves are relatively rare in real systems these days is that (1) the optimality of Hilbert curves is largely based on the assumption of indexing on sequential storage media, and (2) for the many other applications of structures describable by space-filling curves, a Hilbert description is often inferior in practice. For example, it is a suboptimal curve to use if you are implementing spatial analysis operators in a distributed system. If you were designing a spatial indexing system from scratch today for modern applications, you would use neither Hilbert nor Morton/Z curves but they are adequate shortcuts for sufficiently narrow applications. Substantially more optimal curves also have a much more complex description.
- cbsmith 11y ago
  What would you go with for spatial indexing today? R*-tree? k-d tree? BVH?

by Smerity 11y ago

jandrewrogers 11y ago

The primary advantage of Hilbert curves relative to Morton (Z) curves is that they are marginally more efficient at linearizing multidimensional point indexes e.g. storing on spinning disk. However, the reason that Hilbert curves are relatively rare in real systems these days is that (1) the optimality of Hilbert curves is largely based on the assumption of indexing on sequential storage media, and (2) for the many other applications of structures describable by space-filling curves, a Hilbert description is often inferior in practice. For example, it is a suboptimal curve to use if you are implementing spatial analysis operators in a distributed system. If you were designing a spatial indexing system from scratch today for modern applications, you would use neither Hilbert nor Morton/Z curves but they are adequate shortcuts for sufficiently narrow applications. Substantially more optimal curves also have a much more complex description.

cbsmith 11y ago
What would you go with for spatial indexing today? R*-tree? k-d tree? BVH?