Talk:Locality-sensitive hashing

Reference from "Locality preserving hashing"

What is the difference between "Locality-sensitive hashing" and "Locality preserving hashing"? The article of the last one refers to this article, but there is no detailed explanation of the motivation behind the "sensitive" and "preserving" notation. — Preceding unsigned comment added by 92.200.44.109 (talk) 08:50, 30 July 2015 (UTC)

I added a reference to this article that goes into a lot of detail about two specific algorithms, LSH and LPH.

I agree that the difference in terminology (if any) is unclear. What (if anything) is the difference between "sensitive" and "preserving" to a hash function? --DavidCary (talk) 16:52, 22 August 2016 (UTC)

I don't think there's much of a difference. I think we should fold both terms into the same article. Prad Nelluru (talk) 05:12, 17 April 2019 (UTC)

Suggestion to remove Nilsimsa Hash section

The Nilsimsa Hash does not really fit into the LSH definition(s) (Indyk's or Charikar's). Consequently, there is no way to plug into the common framework of LSH and obtain good index-size and query performance guarantees --- one of the strengths of LSH approaches. Hence, I suggest this section should be removed, or at least not in the current place (in the same level with random projection, simhash, and p-stable based lsh).

Is there a name for the more general category that includes Nilsima hash, LSH, LPH, TLSH, etc.? --DavidCary (talk) 16:52, 22 August 2016 (UTC)

Untitled

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

Charikar's definition is too narrow, though a bit easy to understand by beginners.

Do you have a reference to a "better" definition? Please add that reference to the article. Thank you. --DavidCary (talk) 16:52, 22 August 2016 (UTC)

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)

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)

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)

Hey guys, i have a question.

in the last section:

LSH Algorithm for the Nearest Neighbor Search

... it is being claimed that : ....

query time: $O(L(kt+dnP_{2}^{k}))$;

i am trying to figure out from where does the $P_{2}$ comes from... why is the probability for colision is $P_{2}$ ?

can someone please shed some light on this? —Preceding unsigned comment added by Caligola0 (talk • contribs) 18:01, 18 June 2009 (UTC)

I agree -- what is the meaning of $P_{1}$, $P_{2}$, and $d$? --DavidCary (talk) 16:52, 22 August 2016 (UTC)

$d$ is the dimension of the data-points, $P_{1}$ is the probability that two close points (distance $\leq R$) collide. $P_{2}$ the probability that two far points (distance $\geq cR$) collide. --Thomasda (talk) 18:13, 3 November 2021 (UTC)

Relation to Vector Quantization?

hi - could someone clarify the relation to Vector Quantization please? --mcld (talk) 09:21, 8 April 2010 (UTC)

merge

I suggest merging locality-preserving hashing into locality-sensitive hashing. There seems to be enough WP:OVERLAP that a single article can cover both, and clarify the distinction (if any) between them. --DavidCary (talk) 15:50, 22 August 2016 (UTC)

 Done Klbrain (talk) 08:13, 10 May 2018 (UTC)

Random projection

How is $1-x/\pi$ "closely related" to $cos(x)$ for small $x$? It is surely not a Taylor expansion, or anything of that sort. How is this even a relevant comment at this point? — Preceding unsigned comment added by 37.24.141.200 (talk) 21:43, 2 September 2016‎ (UTC)

That's a referenced example of method; I agree that the approximation is not the Taylor expansion, but it is the method used by the paper. The comment about the relationship between $1-x/\pi$ and $cos(x)$ is necessary to support the final statement in the section:"Two vectors' bits match with probability proportional to the cosine of the angle between them". Klbrain (talk) 09:09, 4 April 2018 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Locality-sensitive hashing. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20101203074412/http://www.vision.caltech.edu/malaa/software/research/image-search/ to http://www.vision.caltech.edu/malaa/software/research/image-search/

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 23:13, 4 January 2018 (UTC)

Is Geohash algorithm L-s hashing?

See Geohash. How to proof?

• yes, is Locality-preserving. The global probabilities (to check $R$ and $cR$) are not easy to calculate...
• Amplification? how to check?

Perhaps the easy and first step is to transform Geohash digest from base32 to base4, because Geohash divides globe into 4 regions.