# Find similar vector by Locality Sensitive Hashing

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.

• 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. – D.W. Jul 18 '13 at 20:50
• 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. – D.W. Jul 19 '13 at 5:44

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.