java - How to lookup the most similar bit vector in an prefix tree for NN-search?

Question

The problem I'm trying to solve is explained in this question: Finding the single nearest neighbor using a Prefix tree in O(1)?

My question is regarding the Proposed solution section in that question page. In that section it's mentioned that we find the nearest neighbor from each prefix tree by traversing the tree starting from the node. Well looking up if a key exists in a prefix tree is straightforward but getting the most similar one I don't understand at all. How to accomplish this?

I wish if someone can explain this to me, if not graphically (which is preferred), then at least with some details.

Edit:

here's the code of the paper. It's written in python and unfortunately I never worked with python before. If anybody is familiar with python and can lookup the code to see how they find the nearest neighbors using prefix trees. https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

Answer 1

First know they iterate over the entire tree. By iterating over the entire tree they are guaranteed to find the most similar neighbor.

To be more efficient in the average case use a DFS graph traversal for the tree. Notice that since it is a tree, there will be no need for a coloring scheme for visited nodes.

Start with the closest object as null and at the root of the tree.

For each node you should traverse the children in the order of how much they add to the edit distance and only if the added edit distance would not be greater than the distance to the closest object. For example, with hamming distance, first traverse the child that would add "O" to the overall distance, then afterwards traverse the child that would add "1" to the overall distance. But do not traverse into the "1" child if that would make the edit distance greater than the current closest distance.

When you encounter a "word" within the prefix tree check to see if it has a distance to the query object that is less than the closest object and assign it to closest.