Class VpTree

All Implemented Interfaces:

public class VpTree extends Object implements NearestNeighbor<double[]>

Vantage point tree implementation for nearest neighbor search. The implementation is based on the paper [1] and the C++ implementation from Steve Hanov [2]. This implementation avoids recursion when searching to avoid a possible stack overflow for pathological cases.

The vp-tree is usually 2-3x slower than a kd-tree for a random set of points but it excels in datasets that the kd-tree is weak in - for example points lying on a circle, line or plane. The vp-tree is up to an order of magnitude faster than a kd-tree for these cases. Use this data structure if you hit a pathological case for a kd-tree.

[1] Peter N. Yianilo "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces"
[2] Steve Hanov. see

  • Constructor Details

    • VpTree

      public VpTree(long randSeed)
      randSeed - Random seed
  • Method Details