I used this paper and associated code in my undergraduate thesis. After decoupling the C++ code from MATLAB I was able to make it into a library and use it to search binary features instead of the floating point features hashed with Locality Sensitive Hashing, giving an exact k-NN instead of approximate. The code was fast but the benefits really manifest with large numbers of codes (pretty much what we want). Contact me if you would like to see the performance of this code for various m and image corpuses, or the rest of my paper.

EDIT: also it's probably best to link to the homepage for the paper: http://www.cs.toronto.edu/~norouzi/research/mih/ and the code: https://github.com/norouzi/mih/