5 ms·

Assuming your strings are a lot larger than length 2, you might look at locality-sensitive hashing. If you are using fixed length bit strings, let me know as t

by dalke 11y ago

Assuming your strings are a lot larger than length 2, you might look at locality-sensitive hashing. If you are using fixed length bit strings, let me know as there are other ways to get sublinear search time for NxM searches. Handwave: order your strings in M by popcount. If string n has popcount p then you only need to compare to the m in M which have between p-2 and p+2 bits set. You can subdivide the search space even further. And with newer processors, the POPCNT instruction is your friend.

aktenlage 11y ago
Do you have a suggestion about the case where the hamming distance of the nearest neighbor is unknown? My first thought is to start at the "distance-of-p" block and continue with the "p+i" and "p-i" block in a loop.
- dalke 11y ago
  Yes, that is why my code does.
  - aktenlage 11y ago
    thanks
retbull 11y ago
I thought popcnt has a bug? I am just going off of memory of reading some very indepth blog posts on how it slowed down run times rather than sped them up. I could have forgotten though. Before I even finished this post I just went and found it. Looks like it might be only for haswell and sandy/ivy bridge http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance http://stackoverflow.com/questions/25078285/replacing-a-32-b...
- nkurz 11y ago
  There is a bug that significantly reduces performance if certain register combinations are used, but the current generation of compilers have been patched to avoid triggering it. So it's something you should be on the lookout for, but if you are compiling your own code (or working directly in assembly) it's not a reason to avoid POPCNT. If you are distributing high-performance code that might be compiled with unpatched compilers, you probably should take steps to mitigate. In this case using a snippet of inline assembly where you have control of the registers is probably the best solution, since even if you avoid explicitly using __builtin_popcount() the compiler might "optimize" your algorithm to use it anyway.
  - dalke 11y ago
    My own code is in assembly. Plus, when that came out I tested the different alternatives, and found that my hardware didn't have the problem. Perhaps it was too old. I also did extensive comparisons between the POPCNT version and the nibble-based version using PSHUFB, and showed that the POPCNT version was always faster.
nkurz 11y ago
And with newer processors, the POPCNT instruction is your friend. You probably are aware, but on newer processors with AVX2, using SIMD to count bits can be almost twice as fast as using builtin POPCNT. And if the move to AVX-512 ever happens, this advantage will probably grow. Wojciech has numbers here, although I think he may be slightly understating the advantage: http://wm.ite.pl/articles/sse-popcount.html http://wm.ite.pl/articles/sse-popcount.html
- dalke 11y ago
  Yes. I saw that going around HN recently. I still have it open in a tab. But to me, that new hardware is still a dream.
itodd 11y ago
They are between about 5 and 32 characters. I have converted them to bitstrings (one-hot encoded). They are grouped by length so they are fixed. If you have more information on the algorithm you describe, I would love to hear it. There are not many duplicates in a 1e9 sampling. This is a protein library with a huge diversity for what it's worth.
- Someone 11y ago
  Huh? I cannot reconcile that with what you wrote earlier: "I'm currently trying to find similar strings (max hamming of 2) between two very large (1e9) sets." 'Hamming' I only know as Hamming distance (https://en.m.wikipedia.org/wiki/Hamming_distance https://en.m.wikipedia.org/wiki/Hamming_distance). If that is what you are referring to, the first thing I would do is to divide and conquer by splitting the sets of strings by length (Hamming distance isn't defined for strings of unequal length) After that, I would handle the larger strings by deriving 3 about-equal sized string keys from them. For example, split strings of length 14 in parts of lengths 5, 5, and 4. If two of the strings have Hamming distance <= 2, one of those derived keys must be equal in both strings by the pigeonhole principle. For length 14, and assuming a ACGT alphabet (or am I showing my ignorance here?), that divides and conquers by a factor 256 or 1024. Since the naive "compare all pairs" algorithm is O(nm) for sets of size n and m, respectively, in comparisons, that should get you a speed up of a factor of at least 4 orders of magnitude. Another approach might be to consider all possible pairs of replacements, and check whether they could make the strings equal. For example, assume the errors are that one A got replaced by a C and one T by an A. Then, do a replace all in all strings for those replacements, look for duplicates in the results, and then check the Hamming distances between the original strings that became equal after making those replacements (I would guess it isn't necessary to physically do the string replacements; adjusting the comparison function during sorting may be faster) Again assuming a small alphabet, that should be doable, as all possible pairs of replacements isn't that many pairs. And of course, the two can be combined. (It would be a bit more messy to implement and would give a bit less of a speed up, but I think the gist of the above would work fine if you meant edit distance instead of Hamming distance) Edit: an alternative could be to split each string in trigrams ("abcde" => {"abc", "bcd", "cde"}), index them with some text search engine such as Lucene, using no tokenizer, and then do a billion searches in that set. Anything with few changes will end up high in the search results there, and it is fairly easy to determine hard bounds there. At 10ms per search and 1E9 searches, that would 'only' take 1E8 seconds, or 3 years. It is easily parallelized and distributed, though.

by dalke 11y ago

aktenlage 11y ago

Do you have a suggestion about the case where the hamming distance of the nearest neighbor is unknown? My first thought is to start at the "distance-of-p" block and continue with the "p+i" and "p-i" block in a loop.

dalke 11y ago
Yes, that is why my code does.
- aktenlage 11y ago
  thanks

retbull 11y ago

I thought popcnt has a bug? I am just going off of memory of reading some very indepth blog posts on how it slowed down run times rather than sped them up. I could have forgotten though. Before I even finished this post I just went and found it. Looks like it might be only for haswell and sandy/ivy bridge http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance http://stackoverflow.com/questions/25078285/replacing-a-32-b...

nkurz 11y ago
There is a bug that significantly reduces performance if certain register combinations are used, but the current generation of compilers have been patched to avoid triggering it. So it's something you should be on the lookout for, but if you are compiling your own code (or working directly in assembly) it's not a reason to avoid POPCNT. If you are distributing high-performance code that might be compiled with unpatched compilers, you probably should take steps to mitigate. In this case using a snippet of inline assembly where you have control of the registers is probably the best solution, since even if you avoid explicitly using __builtin_popcount() the compiler might "optimize" your algorithm to use it anyway.
- dalke 11y ago
  My own code is in assembly. Plus, when that came out I tested the different alternatives, and found that my hardware didn't have the problem. Perhaps it was too old. I also did extensive comparisons between the POPCNT version and the nibble-based version using PSHUFB, and showed that the POPCNT version was always faster.

nkurz 11y ago

And with newer processors, the POPCNT instruction is your friend. You probably are aware, but on newer processors with AVX2, using SIMD to count bits can be almost twice as fast as using builtin POPCNT. And if the move to AVX-512 ever happens, this advantage will probably grow. Wojciech has numbers here, although I think he may be slightly understating the advantage: http://wm.ite.pl/articles/sse-popcount.html http://wm.ite.pl/articles/sse-popcount.html

dalke 11y ago
Yes. I saw that going around HN recently. I still have it open in a tab. But to me, that new hardware is still a dream.

itodd 11y ago

They are between about 5 and 32 characters. I have converted them to bitstrings (one-hot encoded). They are grouped by length so they are fixed. If you have more information on the algorithm you describe, I would love to hear it. There are not many duplicates in a 1e9 sampling. This is a protein library with a huge diversity for what it's worth.

Someone 11y ago
Huh? I cannot reconcile that with what you wrote earlier: "I'm currently trying to find similar strings (max hamming of 2) between two very large (1e9) sets." 'Hamming' I only know as Hamming distance (https://en.m.wikipedia.org/wiki/Hamming_distance https://en.m.wikipedia.org/wiki/Hamming_distance). If that is what you are referring to, the first thing I would do is to divide and conquer by splitting the sets of strings by length (Hamming distance isn't defined for strings of unequal length) After that, I would handle the larger strings by deriving 3 about-equal sized string keys from them. For example, split strings of length 14 in parts of lengths 5, 5, and 4. If two of the strings have Hamming distance <= 2, one of those derived keys must be equal in both strings by the pigeonhole principle. For length 14, and assuming a ACGT alphabet (or am I showing my ignorance here?), that divides and conquers by a factor 256 or 1024. Since the naive "compare all pairs" algorithm is O(nm) for sets of size n and m, respectively, in comparisons, that should get you a speed up of a factor of at least 4 orders of magnitude. Another approach might be to consider all possible pairs of replacements, and check whether they could make the strings equal. For example, assume the errors are that one A got replaced by a C and one T by an A. Then, do a replace all in all strings for those replacements, look for duplicates in the results, and then check the Hamming distances between the original strings that became equal after making those replacements (I would guess it isn't necessary to physically do the string replacements; adjusting the comparison function during sorting may be faster) Again assuming a small alphabet, that should be doable, as all possible pairs of replacements isn't that many pairs. And of course, the two can be combined. (It would be a bit more messy to implement and would give a bit less of a speed up, but I think the gist of the above would work fine if you meant edit distance instead of Hamming distance) Edit: an alternative could be to split each string in trigrams ("abcde" => {"abc", "bcd", "cde"}), index them with some text search engine such as Lucene, using no tokenizer, and then do a billion searches in that set. Anything with few changes will end up high in the search results there, and it is fairly easy to determine hard bounds there. At 10ms per search and 1E9 searches, that would 'only' take 1E8 seconds, or 3 years. It is easily parallelized and distributed, though.