Efficient method to compute weighted Jaccard similarity?

Question

I'm looking for pointers for high-performance calculation of the weighted Jaccard similarity between two sparse count vectors. I would like to speed up my code by at least 5x.

I have a database of about 2 million count vectors. Each count vector is sparse, with about 50 non-zero terms in the range 0-(2**32-1). (The number of terms ranges from 1 to 230, the 1st quartile is 41 and the 3rd quartile is 58. The count ranges from 1 to 230.) Technically these are Morgan count fingerprints for molecules, generated by the RDKit cheminformatics toolkit.

The database is used to find similar molecules. Someone enters a molecule, which is converted into a new count vector, and the nearest 100 or so vectors are found, and the associated molecules returned. The similarity could be as low as 0.4 and still be meaningful.

I have previously implemented Jaccard search for the binary case, where the features have been reduced to a bitstring of length 1024 bits or so. I used several papers (eg, 10.1021/ci600358f, 10.1093/comjnl/bxx046, 10.1021/ci200235e) to help get the performance. The second uses AVX2 instructions.

I would like similar pointers for how to improve weighted Jaccard search performance.

Here is what I do now. I store the count vector as a vector of keys and a vector of counts, both uint32_t for now. I store the keys in sorted order.

I want to compute the weighted Jaccard similarity between these vectors. This is defined in the usual way, described at https://en.wikipedia.org/wiki/Jaccard_index#Generalized_Jaccard_similarity_and_distance . The implementation is something like:

intersect_count = sum(min(count1[i], count2[j]))
     where key1[i] == key2[j];
union_count = sum(count1[i]) + sum(count2[j])
similarity = intersect_count / (union_count - intersect_count)

The tricky part is to find where key1[i] == key2[j]. Since I stored them in sorted order, I can compare them like doing a merge sort. If they are equal then I can compute the min of the corresponding counts. Otherwise if key[i] is smaller then I increment i, otherwise I increment j.

Here's the heart of the method

/* earlier, union_count = sum of counts1 and counts2 */
k1 = keys1[f1];
k2 = keys2[f2];
f1 = f2 = 0;

while (1) {
  /* If the two keys match then increase the intersection count */
  /* and advance to the next keys */
  if (k1 == k2) {
    if (counts1[f1] <= counts2[f2]) {
      intersect_count += counts1[f1];
    } else {
      intersect_count += counts2[f2];
    }
    f1++;
    f2++;
    if ((f1 == num_features1) ||
        (f2 == num_features2)) {
        goto end;
    }
    k1 = keys1[f1];
    k2 = keys2[f2];
    continue;
  }
  /* If the first key is smaller, advance it by one */
  if (k1 < k2) {  /* Profiling says 20% of the time is spent here */
    f1++;
    if (f1 == num_features1) {
      goto end;
    }
    k1 = keys1[f1];
    continue;
  } else {
    /* otherwise, advance the other key by one */
    f2++;
    if (f2 == num_features2) {
      goto end;
    }
    k2 = keys2[f2];
    continue;
  }
}
end:
return ((double) intersect_count) / (union_count - intersect_count);

There's are a lot of branches in the code, which surely doesn't help. The profiler shows that 20% of the time is spend on integer comparison, which makes me wonder if vectorized approach, eg, with Intel intrinsics, might help.

Another approach might an inverted index. There is much work on finding the intersection of postings lists, which is related, but I need to find the sum of the intersection of weighted postings. My own attempt resulted in slightly faster code than the brute force one (0.3 instead of 0.5 seconds) but unlike the brute force one it cannot easily be parallelized.

I looked for previous work, since Jaccard similarity is so popular for a wide number of search domains, but failed to find any leads.

In principle a MinHash or other approximation might help, but we already use an approximation technique to map count vectors down to bit vectors for fast unweighted Jaccard search. We want an exact method so we can quantify the effect of the approximations.

I have also looked into LSH, but our similarity threshold is so low (0.5 or so) that I think the methods for high similarity search don't work, and that fast brute force search is the right way to take on the curse of dimensionality.

A suggestion of something to try, or a pointer to existing code, technical paper, or blog entry would be most helpful.

Answer 1

This is exactly the problem for which locality-sensitive hashing was invented. In particular, MinHash looks perfect for your needs. You build up a sort of "index" once, which involves a linear scan through all the 2 million vectors in your database. Then, given a new vector $x$, you can quickly find all matches that have high Jaccard similarity with $x$, using that index -- it is much faster than comparing $x$ to each of the 2 million vectors in your database. You should be able to get huge speedups in this way.