Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 0 down vote accepted

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$.

share|cite|improve this answer
So suppose I choose the right child over the left child, and my tau is distance from the target to the right child. If tau is greater than the distance between the target and the shell of the left child, then I would also search the left child? – mathguy Oct 29 '12 at 14:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.