Package org.ddogleg.nn.alg

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

Nested Class Summary

Nested classes/interfaces inherited from interface org.ddogleg.nn.NearestNeighbor

NearestNeighbor.Search<P>

Constructor Summary

Constructors

Constructor	Description
VpTree(long randSeed)	Constructor

Method Summary

Modifier and Type	Method	Description
NearestNeighbor.Search<double[]>	createSearch()	Creates a new search for this data structure.
void	setPoints(List<double[]> points, boolean trackIndicies)	Specifies the set of points which are to be searched.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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(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.

Specified by:

createSearch in interface NearestNeighbor<double[]>

Returns:

A new search object for this instance.