<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](https://en.wikipedia.org/wiki/Jaccard_index) (*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**: @username_1 - 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).


---

