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

    • setPoints

      public void setPoints(List<double[]> points, boolean trackIndicies)
      Description copied from interface: NearestNeighbor
      Specifies the set of points which are to be searched.
      Specified by:
      setPoints in interface NearestNeighbor<double[]>
      Parameters:
      points - Set of points.
      trackIndicies - If true it will keep track of the index. Making it easy to associate data.

    • createSearch

      public NearestNeighbor.Search<double[]> createSearch()
      Description copied from interface: NearestNeighbor
      Creates a new search for this data structure. This is intended to enabled concurrent searches. After NearestNeighbor.setPoints(List, boolean) has been called and returned, each searched can be called independently in separate threads. Do not call NearestNeighbor.setPoints(List, boolean) which a search is being performed.
      Specified by:
      createSearch in interface NearestNeighbor<double[]>
      Returns:
      A new search object for this instance.