Talk:Locality-sensitive hashing

This is the talk page for discussing improvements to the Locality-sensitive hashing article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Robotics Unassessed

	This article is within the scope of WikiProject Robotics, a collaborative effort to improve the coverage of Robotics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.RoboticsWikipedia:WikiProject RoboticsTemplate:WikiProject RoboticsRobotics
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

Just made the page. There are some variations among definitions of LSH - I am using Charikar's. Flamholz 19:40, 6 June 2007 (UTC)[reply]

Definition of an LSH

I don't think the current definition really makes sense, although maybe it could be modified a little to work.

Specifically: for a metric phi(x,y), we have phi(x,y)->0 (intuitively) as x->y. But if Pr[h(x)=h(y)] -> 0 as x->y, that's bad! I mean, that is just about the opposite of a locality-sensitive hash.

One fix might be to say Pr[h(a) = h(b)] = 1 - phi(a,b) instead.

Although it would also be nice to allow for general boolean combinations of hashes, such as simultaneously hashing to many different values, and calling it a hit if some combination thereof actually collide. —Preceding unsigned comment added by PhiloMath (talk • contribs) 07:14, 5 December 2007 (UTC)[reply]

I totally agree. The definition as it stands is wrong. The phi(a,b) is a similarity not a distance or metric (mathematics). Another error is that the Jaccard_index which is a similarity but is currently is referred to as the "Jaccard distance". Notice that the correct definition looks like a probabilistic version of Injective_mapping. cmobarry (talk) 17:26, 20 December 2007 (UTC)[reply]

Added another variant of LSH definition

We added the Indyk-Motwani definition of the LSH family, plus an LSH family for the Hamming space (by bit sampling), as well as the LSH algorithm for the nearest neighbor search (approximate). Alex and Piotr. 128.30.48.53 (talk) 02:13, 7 February 2008 (UTC)[reply]