# non-binary locality-sensitive hashing with random projections

I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to which side of the hyperplane a data point lies. I want to use locality sensitive hashing with a random projection, but I need to be able to produce more than just two possible indexes.

I'm wondering if I could make an LSH by binning data according to this strategy:

1. Initialize a d x k matrix, where d is the input data dimensionality and k is the number of hash indexes we want.
2. Project incoming data into k-dimensional space using this matrix.
3. Take the argmax of the new k-dimensional vector. In other words, output the dimension that has the largest value.

If not, does anyone know of another technique? Thanks!

• I mean that dimension-wise - the dimension that has the largest value. – aresync Jan 2 '18 at 16:23

Let $h_r(x)$ be a hash function that hashes a point $x$ to a one-bit hash output. Then you can construct a hash function that gives you a $b$-bit hash output, by concatenating $b$ independent one-bit hashes:
$$h_{r_1,\dots,r_b}(x) = (h_{r_1}(x), \dots, h_{r_b}(x)).$$
For example, you can pick $b$ random hyperplanes; then the $i$th bit of the hash will indicate where the point falls relative to the $i$th hyperplane.