# Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity?

With locality sensitive hashing (specifically multi-probe hashing http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf) how are the guarantee of similarity returns made? Why are there multiple tables involved in the hash indexing? Wouldn't that make it LESS probable that an item hashed to a bucket is similar to another rather than the reverse?

• Have you read the paper? Presumably the proof will answer your questions. – Yuval Filmus Oct 29 '18 at 0:45
• From what I saw the paper uses the tables with an implicit knowledge that they somehow make the distinct items that are closer a closer probability based on the "nearness" of the distance metrics chosen from the hash family of functions. Based on their analysis and hash function used, Euclidean distance should be minimalized between 'near' items. – noname Oct 29 '18 at 2:50
• The problem is that they don't seem (from what I saw) to mention how having multiple tables increases the collision property of near items. They mention explicitly that having the series of hash functions INCREASES the distance between both near AND far items (the p1 and p2 probabilities mentioned in the paper) so that the collision property of the two items should be decreased, which is the opposite of what we want for LSH. – noname Oct 29 '18 at 2:52

LSH indexing first concatenates $$k$$ simple hash functions $$h$$ to produce a function $$g$$. Note that $$g$$ is a regular LSH function, only with slightly different parameters. In particular, probabilities of collision decrease for both near and far objects. The new probabilities are $$p'=p^k$$.
Then they take $$L$$ such functions $$g$$ and produce $$L$$ hash tables. Then we search through all the hash tables, one by one. This effectively increases the probability of collision. The new probabilities are $$p''=1-(1-p^k)^L$$. Note that this function has a sigmoid shape.
It may seem weird to first reduce $$p$$ and then increase it. However, the parameters $$k, L$$ are useful knobs for controlling the behavior of the algorithm. You could certainly run with $$k=L=1$$, but larger values may perform better.
Why? Because using a single hash table is not sufficient: you might miss some matches. Suppose that if you use a single hash table, then a lookup has a 50% chance of returning each match that exists (and a 50% chance of failing to find the match). Then you might choose to use 100 hash tables; look up in each table; and combine all the results from all of the lookups: if you find a match in any of the 100 lookups, then you output it. This reduces the chances of missing a valid match: the probability that a valid match is not found in any of the 100 tables is reduced to $$1/2^{100}$$.