Indexing based on Peano-hilbert curve?

Question

I have a x,y,z 3D points stored in MySQL, I would like to ask the regions, slices or point neighbours. Are there way to index the points using Peano-Hilbert curves to accelerate the queries? Or are there more efficient way to store the 3D data in the MySQL?

thanks Arman.

Answer 1

I've personally never went this far, but I used a Z-curve to store 2D points. This worked quite well, and didn't feel the need to try to implement the hilbert curve for better results.

This should allow you to quickly filter out points that certainly are not close by. In an absolute worst case scenario you still need to scan more than 25% of your table to find points within an area.

The way to go about it is to split the x y z in binary and stitch them together into a single value using the curve. I wish I had a SQL script ready, but I just have one for the 2d z-curve which is a much much easier to do.

Edit:

Sorry you might already know all this already and really just looking for SQL samples, but I have some additions:

• I'm not sure the 25% worst case scan is true as well for 3D planes. It might be higher, don't have the brainpower right now to tell you ;).
• This type of Curve will help you find ranges of where you need to search. If you have 2 coordinates, you can convert these to the hilbert-curve number to find out which section of your table you need to look for items that do exactly match your query.
• You might be able to extend this concept to find neighbours, but in order to use the curve you are still 'stuck' to look in ranges.