Content deleted Content added
Elaborating (talk | contribs) Clarifying role of LSH and randomized routing in shared memory implementation/emulation |
m Open access bot: doi added to citation with #oabot. |
||
Line 240:
<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 factor 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 proportional to the [[Cosine similarity#Cosine Distance|cosine distance]] between them.
===Stable distributions===
| |||