3
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ I mean that dimension-wise - the dimension that has the largest value. $\endgroup$
    – aresync
    Commented Jan 2, 2018 at 16:23

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – aresync
    Commented Jan 2, 2018 at 16:26
  • $\begingroup$ @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.) $\endgroup$
    – D.W. ♦
    Commented Jan 2, 2018 at 17:57
  • $\begingroup$ 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. $\endgroup$
    – aresync
    Commented Jan 2, 2018 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.