An implementation of the lookup phase of the locality senstive hashing scheme described in "Similarity Estimation Techniques from Rounding Algorithms" by Moses Charikar (2002). This code will take a set of equal-length bitstrings and perform approximate nearest-neighbor searches against the set in sublinear time.

This code does not hash non bitstring data into bitstring form. You'll have to do that yourself.

To use, first construct an index using CharikarUtil::mkCharikarStripes. Then query the index using CharikarUtil::findNearest. Look at main.cpp for example usage.

////////////////////////////////////////////////////////////////////////////////

The code is written in such a way that it should be very easy to port to pure C.

MIT License.