<p>You are asking for the near neighbor problem for the Jaccard index. If you are ok with some approximation and randomization, I think there exist subquadratic algorithms based on Locality Sensitive Hashing (LSH). LSH schemes based on MinWise independent hashing are known for the Jaccard index: see the <a href="http://web.mit.edu/andoni/www/papers/CACM-article.ps" rel="nofollow">LSH survey</a> by Andoni and Indyk and references therein, plus the <a href="http://www.mit.edu/~andoni/LSH/" rel="nofollow">LSH webpage</a> (which has some code, although I am not sure if there is any for Jaccard specifically). Also see the original <a href="http://www.cs.princeton.edu/courses/archive/spring04/cos598B/bib/BroderCFM-minwise.pdf" rel="nofollow">MinWise hashing paper</a>.</p>

CC BY-SA 3.0
2015-07-25T21:08:10.050Z
2015-07-25T21:08:10.050Z
Sasho Nikolov
<p><strong>Disclaimer:</strong> This is my first question on cstheory.stackexchange.com so please be forgiving.</p>

<p>I have a list of <em>M</em> (<em>M</em> is big, more than 1 million elements) vectors of integers. Each vector can contain <em>0-N</em> sorted numbers from range <em>[0,N-1]</em>.</p>

<p>Now I have a query vector <em>Q</em>, that - similarly to vectors in the list - can contain <em>0-N</em> sorted numbers from range <em>[0,N-1]</em>. I have to find time efficient way of finding all vectors in the table that have <a href="https://en.wikipedia.org/wiki/Jaccard_index" rel="nofollow">Jaccard similarity coefficient</a> (<em>T</em>) of <em>k</em> or more.</p>

<p>In this particular case, Jaccard similarity coefficient between two vectors <em>a</em> and <em>b</em> is defined as:</p>

<pre><code>Tqb = Nqb / (Nq + Nb - Nqb)
</code></pre>

<p>where <em>Nq</em> and <em>Nb</em> are lengths of vectors and <em>Nqb</em> is the number of common elements.
The naive solution is to compute <em>Tqb</em> between <em>Q</em> and every vector from the table and discard those for which <em>Tqb &lt; k</em>. A little bit better solution is to precompute vectors lengths and consider only vectors of length <em>L</em> such that:</p>

<pre><code>T * Nq &lt;= L &lt;= Nq / T
</code></pre>

<p>where <em>Nq</em> is the length of the query vector <em>Q</em>.</p>

<p>Another trick is to notice that out of any</p>

<pre><code>Nq − T * Nq + 1
</code></pre>

<p>elements chosen at random from the query vector <em>Q</em>, at least one must be present in any other vector to achieve a similarity above the threshold <em>k</em>.</p>

<p>After applying those two constraints the algorithm is still too slow. The lower the threshold <em>k</em> is, the more vectors pass constraint filtering and the longer it takes to compute coefficient. But unfortunately 'longer' means here <em>exponentially</em> longer not <em>linearly</em> longer, probably due to exponentially larger number of vectors passing filtering phase. Ideally, I would like to achieve constant time of finding similar vectors, regardless of <em>k</em> or <em>Q</em>. I'm not sure if this is possible, thought.</p>

CC BY-SA 3.0
2015-07-25T18:44:51.553Z
You are not using the standard Jaccard index, which would be Nqb/(Nq + Nb - Nqb) using your notation. Is that on purpose?
Sasho Nikolov
CC BY-SA 3.0
2015-07-25T19:07:23.513Z
@SashoNikolov - my mistake. Thank you for pointing this out.
mnowotka
CC BY-SA 3.0
2015-07-26T11:24:55.437Z
Since the related Jaccard distance is a metric, couldn't one use a tree data structure, e.g. a [M-tree](https://en.wikipedia.org/wiki/M-tree)? See also this related [question](http://scicomp.stackexchange.com/questions/16078/finding-nearest-neighbors-using-jaccard-distance-for-positive-real-valued-vecto) from a different SE site.
chazisop
<approximation-algorithms><optimization><time-complexity><matching><exp-time-algorithms>
Approximate matching in table of integer vectors
mnowotka
# Approximate matching in table of integer vectors

(Asked by: username_0 on 2015-07-25)

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving.
I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain 0-N sorted numbers from range [0,N-1].
Now I have a query vector Q, that - similarly to vectors in the list - can contain 0-N sorted numbers from range [0,N-1]. I have to find time efficient way of finding all vectors in the table that have Jaccard similarity coefficient (T) of k or more.
In this particular case, Jaccard similarity coefficient between two vectors a and b is defined as:
Tqb = Nqb / (Nq + Nb - Nqb)

where Nq and Nb are lengths of vectors and Nqb is the number of common elements.
The naive solution is to compute Tqb between Q and every vector from the table and discard those for which Tqb < k. A little bit better solution is to precompute vectors lengths and consider only vectors of length L such that:
T * Nq <= L <= Nq / T

where Nq is the length of the query vector Q.
Another trick is to notice that out of any
Nq − T * Nq + 1

elements chosen at random from the query vector Q, at least one must be present in any other vector to achieve a similarity above the threshold k.
After applying those two constraints the algorithm is still too slow. The lower the threshold k is, the more vectors pass constraint filtering and the longer it takes to compute coefficient. But unfortunately 'longer' means here exponentially longer not linearly longer, probably due to exponentially larger number of vectors passing filtering phase. Ideally, I would like to achieve constant time of finding similar vectors, regardless of k or Q. I'm not sure if this is possible, thought.

**Tags:** approximation-algorithms, optimization, time-complexity, matching, exp-time-algorithms

> **Comments:**
> **username_1**: You are not using the standard Jaccard index, which would be Nqb/(Nq + Nb - Nqb) using your notation. Is that on purpose?  
> **username_0**: @SashoNikolov - my mistake. Thank you for pointing this out.  
> **username_2**: Since the related Jaccard distance is a metric, couldn't one use a tree data structure, e.g. a [M-tree](https://en.wikipedia.org/wiki/M-tree)? See also this related [question](http://scicomp.stackexchange.com/questions/16078/finding-nearest-neighbors-using-jaccard-distance-for-positive-real-valued-vecto) from a different SE site.  

---

## 1 answers

### Answer by username_1 on 2015-07-25. Score: 3

You are asking for the near neighbor problem for the Jaccard index. If you are ok with some approximation and randomization, I think there exist subquadratic algorithms based on Locality Sensitive Hashing (LSH). LSH schemes based on MinWise independent hashing are known for the Jaccard index: see the [LSH survey](http://web.mit.edu/andoni/www/papers/CACM-article.ps) by Andoni and Indyk and references therein, plus the [LSH webpage](http://www.mit.edu/~andoni/LSH/) (which has some code, although I am not sure if there is any for Jaccard specifically). Also see the original [MinWise hashing paper](http://www.cs.princeton.edu/courses/archive/spring04/cos598B/bib/BroderCFM-minwise.pdf).


---

