1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you read the paper? Presumably the proof will answer your questions. $\endgroup$ – Yuval Filmus Oct 29 '18 at 0:45
  • $\begingroup$ 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. $\endgroup$ – noname Oct 29 '18 at 2:50
  • $\begingroup$ 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. $\endgroup$ – noname Oct 29 '18 at 2:52
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok thanks for the explanation! This is very good. I think the thing I'm still a little confused on is the fact that you have "like" objects colliding and how that is represented by the p''. Like you said, it's a little strange having probabilities decrease and then increase. Can you elaborate on that further? $\endgroup$ – noname Nov 14 '18 at 2:44
  • $\begingroup$ @noname, look at the plot of p'' for, e.g. L=k=5. Notice how f(0.1) is almost 0, and f(0.9) is almost 1. In other words, after the whole procedure with concatenating hash functions and building multiple hash tables, if we pick k and L right, then P1 will have increased and P2 will have decreased, which is all we ever wanted. $\endgroup$ – Karolis Juodelė Nov 14 '18 at 12:11
0
$\begingroup$

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}$.

This is why using multiple hash tables helps. It reduces the chances of errors. It does come at some cost -- you increase the space usage and the time to find matches -- but it can be a useful tradeoff, as a linear increase in space and time leads to an exponential decrease in the error probability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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