Calculate the Hilbert value of a point for use in a Hilbert R-Tree?

data-structures fractals
user89335 picture user89335 · Sep 20, 2008 · Viewed 7.2k times · Source

I have an application where a Hilbert R-Tree (wikipedia) (citeseer) would seem to be an appropriate data structure. Specifically, it requires reasonably fast spatial queries over a data set that will experience a lot of updates.

However, as far as I can see, none of the descriptions of the algorithms for this data structure even mention how to actually calculate the requisite Hilbert Value; which is the distance along a Hilbert Curve to the point.

So any suggestions for how to go about calculating this?

Answer

Mike G. picture Mike G. · Sep 20, 2008

Fun question!

I did a bit of googling, and the good news is, I've found an implementation of Hilbert Value.

The potentially bad news is, it's in Haskell...

http://www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/

It also proposes a Lebesgue distance metric you might be able to compute more easily.

Related questions

What is the difference between Python's list methods append and extend?

What's the difference between the list methods append() and extend()?

Read More
How to remove a key from a Python dictionary?

When deleting a key from a dictionary, I use: if 'key' in my_dict: del my_dict['key'] Is there a one line way of doing this?

Read More
How do I sort a list of dictionaries by a value of the dictionary?

I have a list of dictionaries and want each item to be sorted by a specific value. Take into consideration the list: [{'name':'Homer', 'age':39}, {'name':'Bart', 'age':10}] When sorted by name, it should become: [{'name':'Bart', 'age':10}, {'name':'Homer', …

Read More