Content deleted Content added
Line 227:
| citeseerx = 10.1.1.226.6905
| s2cid = 6468963
}}</ref>) uses an approximation of the [[cosine distance]] between vectors. The technique was used to approximate the NP-complete [[Maximum_cut|MAX-CUT]] problem.<ref name=Charikar2002 />
The basic idea of this technique is to choose a random [[hyperplane]] (defined by a normal unit vector {{mvar|r}}) at the outset and use the hyperplane to hash input vectors.
Given an input vector {{mvar|v}} and a hyperplane defined by {{mvar|r}}, we let <math>h(v) = sgn(v \cdot r)</math>. That is, <math>h(v) = \pm 1</math> depending on which side of the hyperplane {{mvar|v}} lies. This way, each possible choice of a random hyperplane {{mvar|r}} can be interpreted as a hash function <math>h(v)</math>.
| |||