2 ms·
Swamidass and Baldi - http://www.igb.uci.edu/~pfbaldi/download/download.inc.php?pid=175 http://www.igb.uci.edu/~pfbaldi/download/download.inc.php?pi... . With a
by dalke 11y ago
Swamidass and Baldi - http://www.igb.uci.edu/~pfbaldi/download/download.inc.php?pid=175 http://www.igb.uci.edu/~pfbaldi/download/download.inc.php?pi... . With a followup in Nasr, Hirschberg and Baldi - Hashing Algorithms and Data Structures for Rapid Searches of Fingerprint Vectors http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2926297/ http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2926297/ .
Both emphasize the Jaccard-Tanimoto similarity, which is a bit more complicated than the Hamming. The ideas are easily ported to a Hamming search.
The first paper uses the pre-computed popcount, like I mentioned. I don't recall if it also suggests sorting by popcount, but that's what I do. If both {N} and {M} are pre-sorted then you'll improve cache coherency, because the queries for |n|=i all search the same subrange of i-2<=|m|<=i+2. This is also easy to parallelize with OpenMP.
The second paper observes that you can precompute additional information. For example, consider the subset of M where |m| = 100. You could also compute the popcount of just the first 1/2 of each m, or the popcount of the even numbered bits. This must also be within +/-2 of the popcount same subset of your query.
That is, if the first 1/2 of your query had 40 bits set (so the remainder had 60 bits set) then you can only match those {m} where the first 1/2 set between 38 and 42 bits.
The downside of more subdivisions like this is the increased amount of index overhead and the increased number of if/branches. At some point it's faster to just do a brute force linear search.
On my laptop, with 1024 bit strings, I can do 1M x 1M tests (with a high threshold like what you suggest) within a few hours, giving the pruning from just the first paper.
Send me an email (if my HN account name is ${U} then I'm ${U}@${U}scientific.com ) and with some sample data and I'll see if my code works for what you need, and give you a pointer to the code.