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/
[1] https://github.com/putterson/undergrad-thesis/raw/master/mai...
