hwt

Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space

To understand how the data structure works, please see the docs.

Benchmarks

Most recent benchmark for 1-NN:

You can find benchmark output here.

If you would like to run the benchmarks yourself, just run cargo bench at the command line. I recommend using RUSTFLAGS='-C target-cpu=native' cargo bench instead since both linear search and this tree are both significantly faster when using modern instructions.