2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand. You have two sparse vectors, each with only 50 non-zero entries, and it takes you 0.5 seconds to merge those two sorted lists and find the intersection? Something is horribly wrong with your implementation. I don't know what exactly, because coding questions are off-topic here and I don't particularly want to try to understand your code. Can you replace your code with concise pseudocode showing how you currently compute the intersection? It's possible that this is too implementation-specific and so off-topic here. You might also want to do some basic profiling. $\endgroup$ – D.W. Jun 16 '18 at 0:02
  • $\begingroup$ What do you mean by "query"? Perhaps "query" means comparing a single vector to all others in your set? Do you really need to have all of the distances? Is it enough to just find the closest other vector in the set? Is it enough to search whether there exist any other close vectors in the set? I suggest editing your question to state those requirements more clearly. Take a look at MinHash; it might suffice for your needs. $\endgroup$ – D.W. Jun 16 '18 at 0:03
  • $\begingroup$ @D.W. I have one query vector, and I want to find all target vectors from the 2 million or so in my database which have a similarity of at least 0.6. It takes 0.5 seconds to do that search. I would like it to take 0.1 second or less. $\endgroup$ – Andrew Dalke Jun 16 '18 at 5:01
  • $\begingroup$ @D.W. I have updated the text with background (the problem domain is finding similar molecular structures), references to papers which helped with improving unweighted Jaccard performance, and my thoughts about why I'm looking for an exact solution rather than an approximate one. $\endgroup$ – Andrew Dalke Jun 16 '18 at 5:51
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have considered MinHash, LSH, etc. I am concerned about what "high similarity" means. In my field, the similarity for a nearest neighbor can be as low as 0.4 and still be meaningful. The examples for MinHash, etc. seem to refer to documents with much higher similarities. I can't figure out the expected error rate for search at 0.4 similarity. With LSH it's tunable, but those parameters affect the overall performance. Without ground truth I can't tune, so I want to bootstrap by building the exact solution first. $\endgroup$ – Andrew Dalke Jun 16 '18 at 9:47
  • $\begingroup$ @AndrewDalke, it is tunable with MinHash. You need to work through the parameters. The math is not hard; the Wikipedia article describes how the probability of failing to find a good match can be computed. From that, you can figure out, if you use $k$ different hash functions, what is the probability that a valid match is not discovered. I suggest trying to work through it, and if you're still stuck, ask a new question about how to do that computation. $\endgroup$ – D.W. Jun 16 '18 at 21:21
  • $\begingroup$ In particular, if some other vector $y$ has Jaccard similarity at least 0.4 with the query vector $x$, then there is a $0.4$ probability that it has the same MinHash as $x$, so (if you used one hash function) there is a $0.4$ probability that it would be found during the query and a $0.6$ probability that it would not be found. Now what if you had $k=2$ hashtables (each with its own hash function)? $k=3$ hashtables? $\endgroup$ – D.W. Jun 16 '18 at 21:23
  • $\begingroup$ People are offering to pay me money for a fast exact solution. I can certainly implement a faster approximate solution, but that requires a validation step to show that the error rate is 1) acceptable, and 2) better than the current approximation method we use, which converts the count vector into a 1024-bit bitstring and does fast popcounts on those strings. The only way to do that validation is to establish ground truth, which means implementing a (not as fast) exact search anyway. I don't think there's a budget for turning an engineering project with a clear goal into a research project. $\endgroup$ – Andrew Dalke Jun 17 '18 at 19:10
  • $\begingroup$ @AndrewDalke, you can get the error rate down to exponentially small, so it is exact in practice (the chances of an error can be made smaller than the chances of a cosmic ray causing a bit-flip error that causes an error in the algorithm). You're going to need to do the math to figure out the parameters, or post a separate question. This isn't a research project; it's just not that hard. But if you don't like my proposed answer, that's fine; it's up to you. $\endgroup$ – D.W. Jun 17 '18 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.