4 ms·

Any particular reason why you'd use a Hilbert curve instead of, say, a Z curve (https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-orde

Any particular reason why you'd use a Hilbert curve instead of, say, a Z curve (https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve)? Conversion to and from actual coordinates seems much more straightforward for that one (just bit [de]interleaving). I mean, any Quad/Octree/N-dimensional equivalent can have its cells numbered by giving each quadrant/octant/each of the 2^N sub-cells a certain bit combination and then chaining those together as you descend the tree. The Hilbert curve version is just a special case of this with complicated rules for the "sub cell" <-> "bit sequence" mapping. If you were to use a Z curve, the resulting data format and querying algorithm would be exactly identical to the one in the article, just a lot less complicated in the (not presented) details of "where is this child" than the Hilbert version...

digsmahler 8y ago
The "where is this child" query is unaffected by the ordering, whether Z-order, Hilbert, or other. However querying "which children are in this area" requires that you come up with corresponding ranges along the curve. This is where the Hilbert curve is slightly better because in many cases the same area can be covered by fewer ranges. Follow up questions: How do the number of ranges compare with the different orderings? How much does having fewer range segments affect database query performance? Does it make up for the added computational complexity of Hilbert curves? I've not answers, but these can be answered by science.
strlen 8y ago
Amazon Aurora uses Z-order curves. Here's a post about it, including a comparison of Aurora's Z-order curve implementation of spatial indexing with (stock MySQL 5.7) Rtrees: https://aws.amazon.com/blogs/database/amazon-aurora-under-the-hood-indexing-geospatial-data-using-z-order-curves/ https://aws.amazon.com/blogs/database/amazon-aurora-under-th... (Disclaimer: I worked on this project.) I believe Microsoft SQL server uses Hilbert curves: https://docs.microsoft.com/en-us/sql/relational-databases/spatial/spatial-indexes-overview?view=sql-server-2017 https://docs.microsoft.com/en-us/sql/relational-databases/sp...
helsinki 8y ago
https://github.com/trevorprater/pymorton https://github.com/trevorprater/pymorton provides a simple, dependency-free, and efficient Python interface for generating Z-order curves from two and three-dimensional data.

digsmahler 8y ago

The "where is this child" query is unaffected by the ordering, whether Z-order, Hilbert, or other. However querying "which children are in this area" requires that you come up with corresponding ranges along the curve. This is where the Hilbert curve is slightly better because in many cases the same area can be covered by fewer ranges. Follow up questions: How do the number of ranges compare with the different orderings? How much does having fewer range segments affect database query performance? Does it make up for the added computational complexity of Hilbert curves? I've not answers, but these can be answered by science.

strlen 8y ago

Amazon Aurora uses Z-order curves. Here's a post about it, including a comparison of Aurora's Z-order curve implementation of spatial indexing with (stock MySQL 5.7) Rtrees: https://aws.amazon.com/blogs/database/amazon-aurora-under-the-hood-indexing-geospatial-data-using-z-order-curves/ https://aws.amazon.com/blogs/database/amazon-aurora-under-th... (Disclaimer: I worked on this project.) I believe Microsoft SQL server uses Hilbert curves: https://docs.microsoft.com/en-us/sql/relational-databases/spatial/spatial-indexes-overview?view=sql-server-2017 https://docs.microsoft.com/en-us/sql/relational-databases/sp...

helsinki 8y ago

https://github.com/trevorprater/pymorton https://github.com/trevorprater/pymorton provides a simple, dependency-free, and efficient Python interface for generating Z-order curves from two and three-dimensional data.