Locality-sensitive hashing: Difference between revisions

Content deleted Content added
m Remove link that redirects back to this page
Random projection: Imprecise use of 'proportional', should instead by 'within a constant factor'
Line 236:
For two vectors {{mvar|u,v}} with angle <math>\theta(u,v)</math> between them, it can be shown that
 
:<math>Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}.</math>
 
Since the ratio between <math>\frac{\theta(u,v)}{\pi}</math> is proportional toand <math>1-\cos(\theta(u,v))</math>. Inis factat theleast ratio0.87856 iswhen always<math>\theta(u, withinv) a\in factor[0, \pi]</math> of .87856.<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> Meaning, the probability of the 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===