- 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  and the C++ implementation from Steve Hanov . 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.
 Peter N. Yianilo "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces"
 Steve Hanov. see http://stevehanov.ca/blog/index.php?id=130
Nested Class Summary
Constructors Constructor Description
VpTreepublic VpTree(long randSeed)Constructor
randSeed- Random seed
setPointspublic void setPoints(List<double> points, boolean trackIndicies)Description copied from interface:
NearestNeighborSpecifies the set of points which are to be searched.
createSearchpublic NearestNeighbor.Search<double> createSearch()Description copied from interface:
NearestNeighborCreates a new search for this data structure. This is intended to enabled concurrent searches. After
NearestNeighbor.setPoints(java.util.List<P>, boolean)has been called and returned, each searched can be called independently in separate threads. Do not call
NearestNeighbor.setPoints(java.util.List<P>, boolean)which a search is being performed.