Geek Answers Handbook

Peano-Hilbert Indexing?

I have x, y, z 3D points stored in MySQL, I would like to ask regions, slices or points of neighbors. Is there a way to index points using Peano-Hilbert curves to speed up queries? Or is there a more efficient way to store 3D data in MySQL?

thanks to Armand.

+4
source share
2 answers

I personally never went that far, but I used the Z-curve to store two-dimensional points. This worked well enough and did not feel the need to try to implement the Hilbert curve to achieve better results.

This will allow you to quickly filter out points that are, of course, not close. In the worst case scenario, you still need to scan over 25% of your table to find points within the area.

The way to this is to split xyz in binary format and stitch them together into a single value using a curve. I wish I had a SQL script ready, but I have one for the 2d zd curve, which is much easier to do.

Edit

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

  • I'm not sure if scanning is 25% worse for 3D planes. It may be higher, now you do not have the brain power to tell you;).
  • This type of curve helps you find your search ranges. If you have 2 coordinates, you can convert them to a number of Hilbert curves to find out in which part of the table you need to look for elements that exactly match your query.
  • You may be able to expand this concept to find neighbors, but in order to use the curve, you are still “stuck” for searching in ranges.
+1
source

You can probably take the algorithm for creating geohash and extend it to 3 coordinates. Basically, you determine will have a cube of the world of possible three-dimensional points, and then when you add more bits, you narrow the cube. Then you sequentially define it so that the lower left corner has the smallest value, and you can perform range checks, for example:

XXXXa < the_hash < XXXXz
+1
source

More articles:


All Articles