jsat.linear.vectorcollection

Class VPTree<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.VPTree<V>

All Implemented Interfaces:

Serializable, Cloneable, IncrementalCollection<V>, VectorCollection<V>

Direct Known Subclasses:

VPTreeMV

public class VPTree<V extends Vec>
extends Object
implements IncrementalCollection<V>

Provides an implementation of Vantage Point Trees, as described in "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces" by Peter N. Yianilos
VPTrees are more expensive to create, requiring O(n log n) distance computations. However, they work well for high dimensional data sets, and provide O( log n ) query time for search(jsat.linear.Vec, int)
Note: In the original paper, the VP-tree is detailed, and then enhanced to the VPs-tree, and the VPsb-tree, which each add additional optimizations. This implementation is equivalent to the VPsb-tree presented in the original paper.

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	VPTree.VPSelection
static class	VPTree.VPTreeFactory<V extends Vec>

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	VPTree() no-arg constructor for serialization
	VPTree(DistanceMetric dm)
	VPTree(List<V> list, DistanceMetric dm)
	VPTree(List<V> list, DistanceMetric dm, ExecutorService threadpool)
	VPTree(List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection)
	VPTree(List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection, Random rand, int sampleSize, int searchIterations)
	VPTree(List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection, Random rand, int sampleSize, int searchIterations, ExecutorService threadpool)
protected	VPTree(VPTree<V> toClone) Copy constructor

Method Summary

Modifier and Type	Method and Description
VPTree<V>	clone()
int	getMaxLeafSize() Returns the maximum leaf node size.
void	insert(V x) Incrementally adds the given datapoint into the collection
List<? extends VecPaired<V,Double>>	search(Vec query, double range) Searches the space for all vectors that are within a given range of the query vector.
List<? extends VecPaired<V,Double>>	search(Vec query, int neighbors) Searches the space for the k neighbors that are closest to the given query vector
void	setMaxLeafSize(int maxLeafSize) Sets the maximum leaf node size.
int	size() Returns the number of vectors stored in the collection
protected int	splitListIndex(List<Pair<Double,Integer>> S) Determines which index to use as the splitting index for the VP radius

Methods inherited from class java.lang.Object

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

Constructor Detail

VPTree

public VPTree(List<V> list,
              DistanceMetric dm,
              VPTree.VPSelection vpSelection,
              Random rand,
              int sampleSize,
              int searchIterations,
              ExecutorService threadpool)

VPTree

public VPTree(List<V> list,
              DistanceMetric dm,
              VPTree.VPSelection vpSelection,
              Random rand,
              int sampleSize,
              int searchIterations)

VPTree

public VPTree(List<V> list,
              DistanceMetric dm,
              VPTree.VPSelection vpSelection)

VPTree

public VPTree(List<V> list,
              DistanceMetric dm,
              ExecutorService threadpool)

VPTree

public VPTree(List<V> list,
              DistanceMetric dm)

VPTree

public VPTree(DistanceMetric dm)

VPTree

protected VPTree(VPTree<V> toClone)

Copy constructor

Parameters:

toClone - the object to copy

VPTree

protected VPTree()

no-arg constructor for serialization

Method Detail

size

public int size()

Description copied from interface: VectorCollection

Returns the number of vectors stored in the collection

Specified by:

size in interface VectorCollection<V extends Vec>

Returns:

the size of the collection

insert

public void insert(V x)

Description copied from interface: IncrementalCollection

Incrementally adds the given datapoint into the collection

Specified by:

insert in interface IncrementalCollection<V extends Vec>

Parameters:

x - the vector to add to the collection

search

public List<? extends VecPaired<V,Double>> search(Vec query,
                                                  double range)

Description copied from interface: VectorCollection

Searches the space for all vectors that are within a given range of the query vector.

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the vector we want to find others near

range - the search range around our query

Returns:

the list of all vectors within the range of our query. The paired value contains the distance to the query vector.

search

public List<? extends VecPaired<V,Double>> search(Vec query,
                                                  int neighbors)

Description copied from interface: VectorCollection

Searches the space for the k neighbors that are closest to the given query vector

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the vector we want to find neighbors of

neighbors - the maximum number of neighbors to return

Returns:

the list the k nearest neighbors, in sorted order from closest to farthest. The paired value contains the distance to the query vector

splitListIndex

protected int splitListIndex(List<Pair<Double,Integer>> S)

Determines which index to use as the splitting index for the VP radius

Parameters:

S - the non empty list of elements

Returns:

the index that should be used to split on [0, index] belonging to the left, and (index, S.size() ) belonging to the right.

getMaxLeafSize

public int getMaxLeafSize()

Returns the maximum leaf node size. Leaf nodes are used to reduce inefficiency of splitting small lists. If a sublist will fit into a leaf node, a leaf node will be created instead of splitting. This is the maximum number of points that may be used to construct a leaf node.

Returns:

the maximum leaf node size in the tree

setMaxLeafSize

public void setMaxLeafSize(int maxLeafSize)

Sets the maximum leaf node size. Leaf nodes are used to reduce inefficiency of splitting small lists. If a sublist will fit into a leaf node, a leaf node will be created instead of splitting. This is the maximum number of points that may be used to construct a leaf node.
The minimum leaf size is 5 for implementation reasons. If a value less than 5 is given, 5 will be used isntead.

Parameters:

maxLeafSize - the new maximum leaf node size.

clone

public VPTree<V> clone()

Specified by:

clone in interface IncrementalCollection<V extends Vec>

Specified by:

clone in interface VectorCollection<V extends Vec>

Overrides:

clone in class Object