Check out metric trees such as the BK-Tree, VP-Tree or GNATs. They allow for fast nearest neighbor searches, for example querying all items in your database with Hamming Distance h < 2.

I stumbled upon metric trees for nearest neighbor queries in metric spaces some months ago and wrote down notes here:

http://daniel-j-h.github.io/post/nearest-neighbors-in-metric...

Hope that helps.