<p>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 <span class="math-container">$p_1$</span> for close points, and probability <span class="math-container">$p_2$</span> for far points; oftentimes, <span class="math-container">$p_1$</span> and <span class="math-container">$p_2$</span> are both small but constant).  After we concatenate <span class="math-container">$\Theta(\log n)$</span> copies of the hash function (if we choose the constant in the <span class="math-container">$\Theta$</span> appropriately), we get that far points collide with probability <span class="math-container">$p_2^{\Theta(\log n)} = \Theta(1/n)$</span>, whereas near points collide with significantly higher probability.</p>
<p>We want far points to collide with probability <span class="math-container">$\approx 1/n$</span>, 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.)</p>
<p>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 <span class="math-container">$t$</span> close points in every bucket.  In that case, we would want to have about <span class="math-container">$t$</span> 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.</p>
<p>The subroutine you mention is for doing the above <em>when you don't know t</em>.</p>
<p>What the subroutine does is goes through each possible number of hash functions one may wish to concatenate for this particular query (<span class="math-container">$k$</span>).  For each such <span class="math-container">$k$</span>, it looks at the size of the buckets containing the query when concatenating <span class="math-container">$k$</span> 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 <span class="math-container">$k_{best}$</span>.</p>
<p>After finishing the loop, the query is performed with <span class="math-container">$k_{best}$</span> concatenations---in other words, only level <span class="math-container">$k_{best}$</span> of the table is actually looked at.</p>
<p>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.</p>

CC BY-SA 4.0
2022-10-17T18:24:25.060Z
2022-10-17T18:24:25.060Z
SamM
<p>I am trying to understand the fundamentals of multilevel Locality Sensitive Hashing. It is defined in the paper <a href="https://arxiv.org/pdf/1605.02673.pdf" rel="nofollow noreferrer">paper</a> (page no-6).</p>
<p>A Multi-level LSH data structure for <span class="math-container">$S$</span> is set up in the following
way: For each <span class="math-container">$k \in \{0,\cdots,k\}$</span> choose functions <span class="math-container">$g_{k,i}$</span> for <span class="math-container">$1 \le  i \le reps(k)$</span> from <span class="math-container">$\mathcal{H}$</span> independently at
random. Then, for each <span class="math-container">$k \in \{0,\cdots,k\}$</span> build reps(<span class="math-container">$k$</span>) hash tables <span class="math-container">$T_{k,i}$</span> with <span class="math-container">$1 \le i \le reps(k)$</span>. For
a fixed pair <span class="math-container">$k \in \{0,\cdots,k\}$</span> and <span class="math-container">$i \in \{1, . . . ,reps(k)\}$</span>, and each <span class="math-container">$x \in X$</span>, concatenate hash values
<span class="math-container">$\{g_{1,i}(x),\cdots, g_k,i\} \in R^k$</span>
to obtain the hash code <span class="math-container">$h_{k,i}(x)$</span>.</p>
<p><a href="https://i.sstatic.net/ib3IP.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ib3IP.jpg" alt="enter image description here" /></a></p>
<p>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.
<a href="https://i.sstatic.net/NlFS6.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NlFS6.jpg" alt="enter image description here" /></a></p>

<hash-function><near-neighbors>
Query Phase of Multi-Level Hashing
David
# Query Phase of Multi-Level Hashing

(Asked by: username_0 on 2022-09-30)

I am trying to understand the fundamentals of multilevel Locality Sensitive Hashing. It is defined in the paper [paper](https://arxiv.org/pdf/1605.02673.pdf) (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](https://i.sstatic.net/ib3IP.jpg)](https://i.sstatic.net/ib3IP.jpg)

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](https://i.sstatic.net/NlFS6.jpg)](https://i.sstatic.net/NlFS6.jpg)

**Tags:** hash-function, near-neighbors


---

## 1 answers

### Answer by username_1 on 2022-10-17. Score: 2 | Accepted answer

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.


---

