Locality-sensitive hashing: Difference between revisions

Revision as of 14:21, 26 April 2024

Revision as of 08:15, 28 April 2024

Line 238:

:<math>Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}.</math>

Since the ratio between <math>\frac{\theta(u,v)}{\pi}</math> and <math>1-\cos(\theta(u,v))</math> is at least 0.87856 when <math>\theta(u, v) \in [0, \pi]</math> ,<ref name=Charikar2002 /><ref name="Goemans Williamson 1995 pp. 1115–1145">{{cite journal | last1=Goemans | first1=Michel X. | last2=Williamson | first2=David P. | title=Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming | journal=Journal of the ACM | publisher=Association for Computing Machinery (ACM) | volume=42 | issue=6 | year=1995 | issn=0004-5411 | doi=10.1145/227683.227684 | pages=1115–1145| s2cid=15794408 | doi-access=free }}</ref>, the probability of two vectors being on the same side of the random hyperplane is approximately proportional to the [[Cosine similarity#Cosine Distance|cosine distance]] between them.

===Stable distributions===