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

1 Answer

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.

This avoids the need to invent new LSH functions.

• Thanks for your answer! So what you're suggesting would give me b different binary values. Are you saying I should then concatenate them into an integer represented in binary? I should clarify - I chose the argmax technique because it allows me to compute gradients with respect to the LSH. I'm trying to solve a weird optimization problem. – aresync Jan 2 '18 at 16:26
• @aresync, yes, that's correct. You didn't mention any requirement about gradients in the question. I can only answer the question as asked. If you want to know about a situation where you have some requirements on ability to compute the gradient, I suggest asking a new question where you include those additional requirements. Perhaps also clarify what you mean by gradients of a function that produces a discrete output. (That said, I don't understand how the construction in your question meets the requirement either -- it doesn't look particularly nice for computing gradients, either.) – D.W. Jan 2 '18 at 17:57
• Thanks for the clarification. My question was about whether or not my proposed strategy would produce an LSH - that question hasn't been answered yet. I wasn't looking for an alternative strategy unless my method doesn't work. Anyway, gradients can flow through this sort of LSH the same way they flow through maxpooling layers in a neural network, although there are a few ways of doing this. – aresync Jan 2 '18 at 18:42