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 &lt; k. A little bit better solution is to precompute vectors lengths and consider only vectors of length L such that:

T * Nq &lt;= L &lt;= 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 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 by Andoni and Indyk and references therein, plus the LSH webpage (which has some code, although I am not sure if there is any for Jaccard specifically). Also see the original MinWise hashing paper.