|
Hi all, WIkipedia in its article http://en.wikipedia.org/wiki/Locality_Sensitive_Hashing; enumerates a bunch of steps to do after having constructed the hashing functions that compose LSH. In essence i don't understand those steps well, and i don't understand wether the algorithm gives you one NN solution or all the solutions that satisfy that they are a distance lesser than cR. |
|
Not sure if i remember correctly, but when I used it, it was something like that :
For instance if element 14 and element 75 have a hash==10100111, they will be in the same bucket in hashtable. So if you want to obtain the NN of element 14, you look up its hash and you will know from the bucket hashtable[10100111] that element 75 (and probably some others) may be in its neighborhood. Iterating through the L representations, you will quickly build a list of at most L*(n/(2^K)) interesting candidates with a calculable risk of missing a candidate. You can then use this list as the first step for sorting if you want N neighbours. "wether the algorithm gives you one NN solution or all the solutions that satisfy that they are a distance lesser than cR" -> it depends of what you need
(Jan 04 '11 at 03:50)
Guillaume Pitel
Nice answer!
(Sep 27 '11 at 13:28)
Mathieu Blondel
|
