Locality-sensitive hashing: Difference between revisions

Content deleted Content added
Cburke91 (talk | contribs)
Cburke91 (talk | contribs)
multiple -> factor and cited paper where such statement can be found, alongside the paper it references
Line 237:
<math>Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}</math>
 
<math>\frac{\theta(u,v)}{\pi}</math> is proportional to <math>1-\cos(\theta(u,v))</math>. In fact the ratio is always within a multiplefactor of .87856<ref name=Charikar2002 /><ref name="Goemans Williamson 1995 pp. 1115–1145">{{cite journal | last=Goemans | first=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}}</ref>. Meaning the probability of the two vectors being on the same side of the random hyperplane is proportional to the [[Cosine_similarity#Cosine_Distance|cosine distance]] between them.
 
===Stable distributions===