Vantage-point trees. Great structure for nearest neighbour searches.
Bonus tip: When you have a fast distance function (like a hamming distance) and write your tree from scratch in C (which almost automatically means you'll optimise it for your use case), they can become absurdly fast - much faster than the general-purpose nearest neighbour libraries I'm aware of.
Bonus tip: When you have a fast distance function (like a hamming distance) and write your tree from scratch in C (which almost automatically means you'll optimise it for your use case), they can become absurdly fast - much faster than the general-purpose nearest neighbour libraries I'm aware of.