Indexing based on Peano-hilbert curve?

Question

Hello, 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.

Answer 2

You can probably take the algorithm to create a geohash, and extend it to 3 coordinates. Basically, you define would have a world cube of possible 3d points, and then as you add more bits, you narrow down the cube. You then consistently define it so that the lower left hand corner has the smallest value, and you can perform range checks like:

XXXXa < the_hash < XXXXz