math & physics
forsandifs at March 3rd, 2011 07:24 — #1
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?
dirus at March 10th, 2011 13:22 — #2
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"