I am trying to understand the fundamentals of multilevel Locality Sensitive Hashing. It is defined in the paper paper (page no-6).

A Multi-level LSH data structure for $S$ is set up in the following way: For each $k \in \{0,\cdots,k\}$ choose functions $g_{k,i}$ for $1 \le i \le reps(k)$ from $\mathcal{H}$ independently at random. Then, for each $k \in \{0,\cdots,k\}$ build reps($k$) hash tables $T_{k,i}$ with $1 \le i \le reps(k)$. For a fixed pair $k \in \{0,\cdots,k\}$ and $i \in \{1, . . . ,reps(k)\}$, and each $x \in X$, concatenate hash values $\{g_{1,i}(x),\cdots, g_k,i\} \in R^k$ to obtain the hash code $h_{k,i}(x)$.

enter image description here

There are several methods to search the query one of them is single probe as given below. I am not getting the query time of the multilevel hashing works. Do we need to look all the levels in the multilevel hashing or just one will give the answer with high probability. See the algorithm given below. enter image description here


1 Answer 1


In locality-sensitive hashing, we generally concatenate a certain number of independently-drawn hash functions to get a single hash. This is most important for an LSH with a constant collision probability for any pair of points (say probability $p_1$ for close points, and probability $p_2$ for far points; oftentimes, $p_1$ and $p_2$ are both small but constant). After we concatenate $\Theta(\log n)$ copies of the hash function (if we choose the constant in the $\Theta$ appropriately), we get that far points collide with probability $p_2^{\Theta(\log n)} = \Theta(1/n)$, whereas near points collide with significantly higher probability.

We want far points to collide with probability $\approx 1/n$, because then every time we look in a hash bucket we find one far point in expectation. (If we found more far points, we'd waste time comparing to each of them.)

But (and here's where the algorithm you mention comes into play), what happens if there are many close points? Perhaps there are so many close points that we expect to find $t$ close points in every bucket. In that case, we would want to have about $t$ far points in every bucket as well---that wouldn't affect our asymptotics for checking within a bucket, and larger buckets means that we do better on close points, improving the performance of our algorithm.

The subroutine you mention is for doing the above when you don't know t.

What the subroutine does is goes through each possible number of hash functions one may wish to concatenate for this particular query ($k$). For each such $k$, it looks at the size of the buckets containing the query when concatenating $k$ hashes. Note that it doesn't do the comparisons yet, just looks at the sizes. It keeps track of what number of concatenations leads to the fewest comparisons in a variable $k_{best}$.

After finishing the loop, the query is performed with $k_{best}$ concatenations---in other words, only level $k_{best}$ of the table is actually looked at.

So to answer your question directly. Only one level of the hash table is actually looked in to answer the query (in only one level do we actually compare to stored data points). But, all levels are scanned for the purpose of seeing which level would be most efficient to query.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.