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

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.