# Locality-sensitive hashing random projection

I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that will be used for the random projection. So, in LSH for Cosine Similarity, the define the hash function $h_i(\vec{v}) = 1$ only if $\vec{r_i} \cdot \vec{v} \geq 0$ and $h_i(\vec{v}) = 0$ only if $\vec{r_i} \cdot \vec{v} < 0$. There are a lot of places that mention that this dot product of $\vec{v}$ and $\vec{r_i}$ means which side of the line (assuming a 2D dimension for instance) the point in question $\vec{v}$ is (negative for one side and positive for the other side), just like in the image below:

However, to my understanding, what will give which side of the line where the point $\vec{v}$ is, is the dot product of the norm of the $\vec{r_i}$ (let's say that the norm is $\vec{n}$) and the vector $\vec{v}$, so the correct wouldn't be the equation $\vec{n_i} \cdot \vec{v}$ instead of $\vec{r_i} \cdot \vec{v}$ ?

No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The set of points $v$ such that $v \cdot r = 0$ is a line; the set of points $v$ such that $v \cdot r \ge 0$ is a half-plane (e.g., the half-plane above that line).
• @Tarantula, draw a picture. Draw the line -- the set of points $v$ such that $v \cdot (4,4) = 0$. Try it. It's not where you think it is. Where you're going wrong is your talking about "on which side of the vector r"; that's not what is meant. Instead about "which side of the line" you're on, which is not the same thing. – D.W. Aug 5 '16 at 15:53