Class VPTree

source code

object --+    
         |    
MetricTree --+
             |
            VPTree

A "Vantage Point Tree" is a static, balanced, binary tree which can be used to index metric spaces with a non-discrete distance function. It has been independently described by both Jeffrey K. Uhlmann (1991) and Peter Yianilos (1993).

Construction is done by picking one object (the "vantage point") from the set of objects to index and then determining the distance of all remaining objects to the vantage point. The median distance is calculated and the set of remaining objects is split in two: objects whose distance to the vantage point is smaller than the median distance and the rest (objects whose distance to the vantage point is larger than or equal to the median). Yianilos called this process "ball decomposition". For both of the resulting sets new child nodes, called "left" and "right", are created recursively. The vantage point and the previously calculated median distance are stored in the current node.

When searching a node, the distance between the current node's value and the search object is calculated. If it is <= k (the given maximum distance), this node's value is added to the list of search results. Searching proceeds recursively into the left subtree if distance - k < median and into the right subtree if distance + k >= median.

Since the construction phase takes advantage of the median of all distances, VPTrees do a fairly good job of balancing their subtrees. Only the fact that you have to put all objects whose distance to the vantage point equals the median distance always have to be put on the same side makes VPTrees tend to hang to the side containing these objects when using discrete distance functions.

Runtime complexity for the construction phase is O(n log(n)), searching is O(log(n)). Space requirement is O(n).