org.ddogleg.nn.alg

Class VpTree<PointData>

java.lang.Object

org.ddogleg.nn.alg.VpTree<PointData>

Type Parameters:

PointData - Type of user data attached to each point

All Implemented Interfaces:

NearestNeighbor<PointData>

public class VpTree<PointData>
extends java.lang.Object
implements NearestNeighbor<PointData>

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 Summary

Constructors

Constructor and Description
VpTree(long randSeed) Constructor

Method Summary

Modifier and Type	Method and Description
void	findNearest(double[] target, double maxDistance, int numNeighbors, FastQueue<NnData<PointData>> results) Searches for the N nearest neighbor to the specified point.
boolean	findNearest(double[] point, double maxDistance, NnData<PointData> result) Searches for the nearest neighbor to the specified point.
void	init(int pointDimension) Initializes data structures.
void	setPoints(java.util.List<double[]> points, java.util.List<PointData> data) Specifies the set of points which are to be searched.

Methods inherited from class java.lang.Object

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

Constructor Detail

VpTree

public VpTree(long randSeed)

Constructor

Parameters:

randSeed - Random seed

Method Detail

findNearest

public void findNearest(double[] target,
                        double maxDistance,
                        int numNeighbors,
                        FastQueue<NnData<PointData>> results)

Description copied from interface: NearestNeighbor

Searches for the N nearest neighbor to the specified point. The neighbors must be within maxDistance.

NOTE: How distance is measured is not specified here. See the implementation's documentation. Euclidean distance squared is common.

Specified by:

findNearest in interface NearestNeighbor<PointData>

Parameters:

target - A point being searched for.

maxDistance - Maximum distance (inclusive, e.g. d ≤ maxDistance) the neighbor can be from point. Values < 0 will be set to the maximum distance.

numNeighbors - The number of neighbors it will search for.

results - Storage for the result. Must be empty before calling. Must support grow() function.

init

public void init(int pointDimension)

Description copied from interface: NearestNeighbor

Initializes data structures.

Specified by:

init in interface NearestNeighbor<PointData>

Parameters:

pointDimension - Dimension of input data

setPoints

public void setPoints(java.util.List<double[]> points,
                      java.util.List<PointData> data)

Description copied from interface: NearestNeighbor

Specifies the set of points which are to be searched.

Specified by:

setPoints in interface NearestNeighbor<PointData>

Parameters:

points - Set of points.

data - (Optional) Associated data. Can be null.

findNearest

public boolean findNearest(double[] point,
                           double maxDistance,
                           NnData<PointData> result)

Description copied from interface: NearestNeighbor

Searches for the nearest neighbor to the specified point. The neighbor must be within maxDistance.

NOTE: How distance is measured is not specified here. See the implementation's documentation. Euclidean distance squared is common.

Specified by:

findNearest in interface NearestNeighbor<PointData>

Parameters:

point - A point being searched for.

maxDistance - Maximum distance (inclusive, e.g. d ≤ maxDistance) a neighbor can be from point. Values < 0 will be set to the maximum distance.

result - Storage for the result.

Returns:

true if a match within the max distance was found.