6 ms·

I'm currently trying to find similar strings (max hamming of 2) between two very large (1e9) sets. Approximate Nearest Neighbor search makes this just barely ma

by itodd 10y ago

I'm currently trying to find similar strings (max hamming of 2) between two very large (1e9) sets. Approximate Nearest Neighbor search makes this just barely manageable. Annoy[0] from Spotify deserves a look for anyone who is outgrowing traditional nearest neighbor algorithms. [0] https://github.com/spotify/annoy https://github.com/spotify/annoy

dalke 10y 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 10y 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 10y ago
    Yes, that is why my code does.
    - aktenlage 10y ago
      thanks
- retbull 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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.
cjauvin 10y ago
Have you looked at the simhashing/minhashing techniques for that?
joshvm 10y ago
What are you running this on and how fast do you need it to be? You can brute force nearest-neighbours on a GPU pretty quickly (many times faster than approximate on a CPU). I was able to do nearest-neighbour from each pixel in an image O(1e6) to a list of keypoint locations O(1e4) in about 50ms on an old GPU compared to minutes of CPU time. It's a much smaller dataset, but still a simple way of getting a huge speedup over CPU alone. Also unlike Annoy or Flann, the results are guaranteed to be exact. (It's also incredibly simple to implement). See for example: https://stackoverflow.com/questions/24020409/producing-a-nearest-neighbour-distance-map-for-a-set-of-points https://stackoverflow.com/questions/24020409/producing-a-nea... EDIT: I saw below that you can split the strings by length which will shorten the time considerably.
putterson 10y ago
I applied a technique for quickly finding exact k nearest neighbors or nearest neighbors in a specific hamming distance using research[0] which includes a library + source code. The largest dataset that I tested was 10M 256 bit codes but the technique scales well with larger datasets. You can look at the performance figures I achieved in my paper at [1]. [0] http://www.cs.toronto.edu/~norouzi/research/mih/ http://www.cs.toronto.edu/~norouzi/research/mih/ [1] https://github.com/putterson/undergrad-thesis/raw/master/main.pdf https://github.com/putterson/undergrad-thesis/raw/master/mai...

by itodd 10y ago

dalke 10y 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 10y 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 10y ago
  Yes, that is why my code does.
  - aktenlage 10y ago
    thanks
retbull 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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.

cjauvin 10y ago

Have you looked at the simhashing/minhashing techniques for that?

joshvm 10y ago

What are you running this on and how fast do you need it to be? You can brute force nearest-neighbours on a GPU pretty quickly (many times faster than approximate on a CPU). I was able to do nearest-neighbour from each pixel in an image O(1e6) to a list of keypoint locations O(1e4) in about 50ms on an old GPU compared to minutes of CPU time. It's a much smaller dataset, but still a simple way of getting a huge speedup over CPU alone. Also unlike Annoy or Flann, the results are guaranteed to be exact. (It's also incredibly simple to implement). See for example: https://stackoverflow.com/questions/24020409/producing-a-nearest-neighbour-distance-map-for-a-set-of-points https://stackoverflow.com/questions/24020409/producing-a-nea... EDIT: I saw below that you can split the strings by length which will shorten the time considerably.

putterson 10y ago

I applied a technique for quickly finding exact k nearest neighbors or nearest neighbors in a specific hamming distance using research[0] which includes a library + source code. The largest dataset that I tested was 10M 256 bit codes but the technique scales well with larger datasets. You can look at the performance figures I achieved in my paper at [1]. [0] http://www.cs.toronto.edu/~norouzi/research/mih/ http://www.cs.toronto.edu/~norouzi/research/mih/ [1] https://github.com/putterson/undergrad-thesis/raw/master/main.pdf https://github.com/putterson/undergrad-thesis/raw/master/mai...