Matlab : Conceptual difficulty in How to create multiple hash tables in Locality sensitive Hashing

Question

The key idea of Locality sensitive hashing (LSH) is that neighbor points, v are more likely mapped to the same bucket but points far from each other are more likely mapped to different buckets. In using Random projection, if the the database contains N samples each of higher dimension d, then theory says that we must create k randomly generated hash functions, where k is the targeted reduced dimension denoted as g(**v**) = (h_1(v),h_2(v),...,h_k(v)). So, for any vector point v, the point is mapped to a k-dimensional vector with a g-function. Then the hash code is the vector of reduced length /dimension k and is regarded as a bucket. Now, to increase probability of collision, theory says that we should have L such g-functions g_1, g_2,...,g_L at random. This is the part that I do not understand.

Question : How to create multiple hash tables? How many buckets are contained in a hash table?

I am following the code given in the paper Sparse Projections for High-Dimensional Binary Codes by Yan Xia et. al Link to Code

In the file Coding.m

dim = size(X_train, 2);
R = randn(dim, bit);

% coding
B_query = (X_query*R >= 0);
B_base = (X_base*R >=0);   

X_query is the set of query data each of dimension d and there are 1000 query samples; R is the random projection and bit is the target reduced dimensionality. The output of B_query and B_base are N strings of length k taking 0/1 values. Does this way create multiple hash tables i.e. N is the number of hash tables? I am confused as to how. A detailed explanation will be very helpful.

Answer 1

How to create multiple hash tables?

LSH creates hash-table using (amplified) hash functions by concatenation:

g(p) = [h₁(p), h₂(p), · · · , h_k (p)], h_i ∈_R H

g() is a hash function and it corresponds to one hashtable. So we map the data, via g() to that hashtable and with probability, the close ones will fall into the same bucket and the non-close ones will fall into different buckets.

We do that L times, thus we create L hashtables. Note that every g() is/should most likely to be different that the other g() hash functions.

Note: Large k ⇒ larger gap between P₁, P₂. Small P₁ ⇒ larer L so as to find neighbors. A practical choice is L = 5 (or 6). P₁ and P₂ are defined in the image below:

How many buckets are contained in a hash table?

Wish I knew! That's a difficult question, how about sqrt(N) where N is the number of points in the dataset. Check this: Number of buckets in LSH

The code of Yan Xia

I am not familiar with that, but from what you said, I believe that the query data you see are 1000 in number, because we wish to pose 1000 queries.

k is the length of the strings, because we have to hash the query to see in which bucket of a hashtable it will be mapped. The points inside that bucket are potential (approximate) Nearest Neighbors.