What is the effect of quantization bucket width in Locality Sensitive Hashing?

Question

In the LSH Tutorial by Slaney, it is written that

Increasing the quantization bucket width w will increase the number of points that fall into each bucket. To obtain our final nearest neighbor result we will have to perform a linear search through all the points that fall into the same bucket as the query, so varying w effects a trade-off between a larger table with a smaller final linear search, or a more compact table with more points to consider in the final search.

As per my understanding, if the bucket size is large, then there should be less number of tables (each bucket is a table right ? ). Since, each point is hashed to a cuket. If a query is hashed to a bucket, then with a linear scan on a larger table, wouldn't it encounter more points than a compact table ?

Answer 1

I think you've got the point, but that you are getting confused by the additional tables that you think should be used to implement buckets.

Let's rephrase the quote from the tutorial first:

In LSH, you create a partition of the entire space. If you use a large bucket width $w$, then obviously you need less buckets to span the entire space and thus you get shorter codes. Since you have less buckets, your hash table has less slots (obvious) but there are also more points per bucket.

Note that by definition of LSH all the points $x$ that fall into a given bucket $B$ have the same binary code: $$\forall x \in B, \text{LSH}(x) = b,$$ where $b$ is some constant.

Now, let's consider what happens when you make a query on the hash table: if you use $b$ as query to the hash table, you will get all the points $x$ in the above formula. The only information that you have on these points is that their binary code is equal to $b$, you do not have additional information: they may be all around the bucket, or in its center, etc. So, you can't avoid comparing your exact query point with each of them (using their real coordinates) if you want to find a special neighbour (usually the closest one).

Since you need to loop over all the points inside the bucket, this search is linear, and here comes the trade-off mentioned in the tutorial.

When you implement some LSH, you are free to use whatever technique you want for both the hash table and the buckets. In my hashing implementation, the hash table was actually a table (for simplicity, because finding a bucket becomes then a simple table lookup), but the buckets themselves were implemented as lists for memory efficiency (you allocate a slot only when you add a point to the bucket).

Your question implies that you would implement the buckets themselves as arrays, but this may not always be desirable when you do not know anything about the distribution of the points in your data set or when your programming framework (in my case, vanilla C/C++) does not allow you to easily resize arrays.