Help in understanding search of Vantage-Point tree This is my reference: < A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It builds this tree by picking a point from a set of points (called the vantage point). The median distance from that point to all other points in space is sort of the boundary that splits off that set into two equally sized subsets. This is repeated recursively for each subset that was made until no more points are left (when all points have been made vantage points). Now searching a VP-tree is where I need help understanding. Basically, when a search is done, a new point is plotted into that space of points, and you need to find the n-nearest neighbors to that point. I especially have a problem with the "tau." and its purpose in this algorithm.

I think what may be confusing you is that he talks about "the farthest point that we have found" but actually means the farthest point of the up to $n$ candidates we've collected so far. Once we've collected $n$ candidates, we can prune all parts of the tree that contain only points worse than the worst of those candidates. To do that, we need to keep track of the distance to our worst candidate so far. That's $\tau$.