Approximate matching in table of integer vectors

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.

• You are not using the standard Jaccard index, which would be Nqb/(Nq + Nb - Nqb) using your notation. Is that on purpose? Jul 25 '15 at 18:44
• @SashoNikolov - my mistake. Thank you for pointing this out. Jul 25 '15 at 19:07
• Since the related Jaccard distance is a metric, couldn't one use a tree data structure, e.g. a M-tree? See also this related question from a different SE site. Jul 26 '15 at 11:24