2

I have a hilbert curve index based on this algorithm. I take two to four values (latitude, longitude, time in unix format and an id code) and create a 1-d hilbert curve.

I'm looking for a way to use this data to create a bounding box query (i.e. "find all ids within this rectangle).

I'm looking for a way to do so without decoding the 1d Hilbert code back into its constituent parts.

My question is: if I created a 2d hilbert curve range (i.e. I converted the range of the box into a hilbert curve so x1y1-> hilbert value1 and x2y2-> hilbertvalue2) would all values of corresponding 2d hilbert values fall within their range?

E.g. If I converted (1,2) and (20,30) into Hilbert values and then searched for all values between hilbertvalue1 and hilbertvalue2, would all the values I get decode to fall within (1,2) and (20, 30), or would I have to perform additional transformations?

When I set all my values to 2^a* X and 2^a * y (a being a positive integer multiplier) it seems to be true. However, is there a way to use a range search on the 4d hilbert curve? I.e., if I have a Hilbert Curve made of 4 values and I have a bounding box query, can I see which hilbert values fall within that bounding box without decoding the entire Hilbert curve and checking?

Thanks.

John Horus
  • 21
  • 2
  • for dimensions of 2, no, look at an 4x4 grid with hilbert numbers, you can imagine drawing rectangles on this grid where the hilbert curve goes "outside" the rectangle. see also https://www.intechopen.com/books/current-trends-and-challenges-in-rfid/efficient-range-query-using-multiple-hilbert-curves – don bright Feb 03 '19 at 03:37

1 Answers1

0

I just found the answer in this paper: https://www.researchgate.net/publication/3296936_Analysis_of_the_Clustering_Properties_of_Hilbert_Space-filling_Curve

It is a dense paper, so I don't have the exact answer. But if you're motivated you can find it !

PS: you can also find the paper here

rambi
  • 215