Class VpTree

java.lang.Object
org.ddogleg.nn.alg.VpTree
All Implemented Interfaces:
NearestNeighbor<double[]>

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"
http://aidblab.cse.iitm.ac.in/cs625/vptree.pdf
[2] Steve Hanov. see http://stevehanov.ca/blog/index.php?id=130

  • Constructor Details

    • VpTree

      public VpTree​(long randSeed)
      Constructor
      Parameters:
      randSeed - Random seed
  • Method Details