Perfect and Minimal Spatial Hashing

3d4dd3f695ae8dec30b9632dc67a8dd9
0
forsandifs 101 Mar 03, 2011 at 12:24

I am reading the following paper: http://research.microsoft.com/en-us/um/people/hoppe/perfecthash.pdf

I think the idea it presents is summarised by the figures at the top of the paper. I think the idea is a way of mapping non uniformly spatially distributed data to a uniformly distributed minimal hash table.

I think it does this by using a hash function of the form: h(p) = h0(p) + O[h1(p)] , where h is an index in the hash table, p(x,y,z) are the spatial coordinates of the data point we wish to hash, and O is an offset table smaller than the hash table itself.

But that’s as far as my “understanding” of the paper goes.

They keep saying how simple their method is but I don’t find their explanation of how to actually implement this simple at all. What are the functions for h0 and h1? How do we calculate the size of h and O and the offset values for O?

1 Reply

Please log in or register to post a reply.

C1976d238771cefea55f9ab920c47575
0
Dirus 101 Mar 10, 2011 at 18:22

From a quick scan of the document, it looks to me like h0, h1 & O are explained in “3.1 Overview & Terminology”. The Value of the Offset Table “O” is explained in “4.3 Creation of Offset Table”