Locality-sensitive hashing: Difference between revisions

Content deleted Content added
Hou8547 (talk | contribs)
Random projection: Correct some typos: (1) the constant is off by a factor of 2; (2) probability of being on *different* sides.
Line 237:
:<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.87856439 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 samedifferent sidesides of the random hyperplane is approximately proportional to the [[Cosine similarity#Cosine Distance|cosine distance]] between them.
 
===Stable distributions===