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 wit

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-spaces/ http://daniel-j-h.github.io/post/nearest-neighbors-in-metric... Hope that helps.