4
$\begingroup$

I have many vectors in my database. They are in high dimensions such as:

  • $v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$
  • $v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$
  • ...

I will use Hamming distance to calculate their difference: The difference between $v_1$ and $v_2$ is $4$ because elements $3$ and $4$ are the same and others are difference.

Now, I want to use Locality Sensitive Hashing (LSH) to put those vectors into different bins.

What kind of hash function can I use for this case?

I have read some article about universal hash function, but I am not sure can I use it and how to ensure that the probability for the similar vectors going to the same bin is higher than those non-similar one.

Here is the way that I think how should I use the universal hash function for my task.

I will first divide those high dimensions vectors into sub-vectors: $$x : 23, 23 \; | \; 1, 33 \; | \; 103, 219 \; | \; \dots$$

sub1-x : 23 23
sub2-x : 1 33
sub3-x : 103 219

The following function will be used for each sub-vector: $$sum_{i=0}^{r} a_{i}x_{i} \mod m$$

Basically this is a dot product, a = {a_1, a_2, ... a_i}, x = {23, 23, 1, 33, 103, 219 ...}, m is a prime.

  • Different combination of {a} will form a different hash table, one hash table is used for one sub-vector.
  • I can now hash the data into bins, but the question is

    Is this an LSH method? I don't know that two similar vectors will go into the same bin with a high probability.

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to the site, sflee! 1. What have you tried? Have you read about LSH? What LSH hash functions have you considered? 2. You haven't provided us enough information to suggest a hash function. What notion of "similarity" do you have in mind? What space do the vectors come from? I suggest you edit your question to provide more details on both of these. Also, I encourage you to read the FAQ for more information on how to ask good questions and how to use this site. $\endgroup$
    – D.W. ♦
    Commented Jul 18, 2013 at 20:50
  • $\begingroup$ Thank you for the edit, sflee! That's a good improvement. My next query to you: Have you done any reading about work on LSH? For instance, have you read the Wikipedia article? Have you done a Google search? Have you tried any of the LSH hash functions you found in your reading? Did they meet your requirements? If not, how did they fall short? Generally, this site expects people to show evidence of research they have done in their question, so I suggest editing your question to incorporate that. $\endgroup$
    – D.W. ♦
    Commented Jul 19, 2013 at 5:44

1 Answer 1

Reset to default
4
$\begingroup$

Yes. This is one plausible method, if you want to find pairs of vectors that are very close to each other. Two vectors that are close in Hamming distance are likely to end up in the same bin at some point.

Suppose two vectors $v,w$ agree in fraction $p$ of their coordinates (where $0\le p \le 1$). Then, heuristically, if we look at a pair of coordinates, the probability that $v,w$ agree on those coordinates is $p^2$; and if we choose those two coordinates for hashing, then $v,w$ will end up in the same bin. If you hash each vector $n$ times, choosing a random pair of coordinates each time, then with probability $1-(1-p^2)^n$, there will be at least one time when they show up in the same bin.

For instance, if two vectors agree on half of their coordinates, and if you hash them 10 times, then 94% of the time they will end up in the same bin for at least one of those 10 hashes.

To know how well it will work on your particular application, you may need to try it (or at least work out the parameters of how close vectors will be, when they are close; how many dimensions they have; how many times you will hash them; etc.).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much. I have think about it and have a question. It seems that no matter my hash function is universal or not, I just need to divide my vectors and project them, then those similar vectors will hash in the same bin with the probability related with their similarity. Am I right? $\endgroup$
    – sflee
    Commented Jul 21, 2013 at 14:02
  • $\begingroup$ @sflee, yes, that's correct. You can use any reasonable hash function for hashing the pair-of-coordinates; it doesn't need to be universal. (Theorists like universal hashes because they have nice theoretical properties, but in practice, you can use any good hash.) $\endgroup$
    – D.W. ♦
    Commented Jul 21, 2013 at 17:29
  • $\begingroup$ What is the nice theoretical properties? Is that because the universal hash function can make an uniform distribution for the indices independently with the input keys? $\endgroup$
    – sflee
    Commented Jul 22, 2013 at 23:35

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.