jsat.linear.vectorcollection

Class VPTree<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.VPTree<V>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, DualTree<V>, IncrementalCollection<V>, VectorCollection<V>

Direct Known Subclasses:

VPTreeMV

public class VPTree<V extends Vec>
extends java.lang.Object
implements IncrementalCollection<V>, DualTree<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 VectorCollection.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.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	VPTree.VPSelection

Nested classes/interfaces inherited from interface jsat.linear.vectorcollection.DualTree

DualTree.DualTreeTraversalAction, DualTree.SelfAsChildNode<N extends IndexNode<N>>

Field Summary

Fields inherited from interface jsat.linear.vectorcollection.DualTree

COMP_SCORE

Constructor Summary

Constructors

Constructor and Description
VPTree()
VPTree(DistanceMetric dm)
VPTree(DistanceMetric dm, VPTree.VPSelection sampling)
VPTree(java.util.List<V> list, DistanceMetric dm)
VPTree(java.util.List<V> list, DistanceMetric dm, boolean parallel)
VPTree(java.util.List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection)
VPTree(java.util.List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection, java.util.Random rand, int sampleSize, int searchIterations)
VPTree(java.util.List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection, java.util.Random rand, int sampleSize, int searchIterations, boolean parallel)

Method Summary

Modifier and Type	Method and Description
void	build(boolean parallel, java.util.List<V> list, DistanceMetric dm) Builds this metric index from the given collection of points using the given distance metric.
VPTree<V>	clone()
V	get(int indx) Accesses a vector from this collection via index.
java.util.List<java.lang.Double>	getAccelerationCache()
DistanceMetric	getDistanceMetric()
int	getMaxLeafSize() Returns the maximum leaf node size.
IndexNode	getRoot()
void	insert(V x) Incrementally adds the given datapoint into the collection
void	search(Vec query, double range, java.util.List<java.lang.Integer> neighbors, java.util.List<java.lang.Double> distances) Performs a range search of the current collection.
void	search(Vec query, int numNeighbors, java.util.List<java.lang.Integer> neighbors, java.util.List<java.lang.Double> distances) Performs k-Nearest Neighbor search of the current collection.
void	setDistanceMetric(DistanceMetric dm) Sets the distance metric used for this collection.
void	setMaxLeafSize(int maxLeafSize) Sets the maximum leaf node size.
int	size() Returns the number of vectors stored in the collection

Methods inherited from class java.lang.Object

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

Methods inherited from interface jsat.linear.vectorcollection.DualTree

computeKnnBound, dist, dual_depth_first, search, search, traverse

Methods inherited from interface jsat.linear.vectorcollection.VectorCollection

build, build, build, getVecs, search, search, search, search

Constructor Detail

VPTree

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

VPTree

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

VPTree

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

VPTree

public VPTree(java.util.List<V> list,
              DistanceMetric dm,
              boolean parallel)

VPTree

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

VPTree

public VPTree()

VPTree

public VPTree(DistanceMetric dm)

VPTree

public VPTree(DistanceMetric dm,
              VPTree.VPSelection sampling)

Method Detail

getRoot

public IndexNode getRoot()

Specified by:

getRoot in interface DualTree<V extends Vec>

build

public void build(boolean parallel,
                  java.util.List<V> list,
                  DistanceMetric dm)

Description copied from interface: VectorCollection

Builds this metric index from the given collection of points using the given distance metric.

Specified by:

build in interface VectorCollection<V extends Vec>

Parameters:

parallel - true if the index should be built in parallel, or false if it should be done in a single thread.

list - the list of vectors to put into the index

dm - the distance metric to build the index using.

setDistanceMetric

public void setDistanceMetric(DistanceMetric dm)

Description copied from interface: VectorCollection

Sets the distance metric used for this collection.

Specified by:

setDistanceMetric in interface VectorCollection<V extends Vec>

Parameters:

dm - the distance metric to use

getDistanceMetric

public DistanceMetric getDistanceMetric()

Specified by:

getDistanceMetric in interface VectorCollection<V extends Vec>

Returns:

the distance metric to use

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

get

public V get(int indx)

Description copied from interface: VectorCollection

Accesses a vector from this collection via index.

Specified by:

get in interface VectorCollection<V extends Vec>

Parameters:

indx - the index in [0, VectorCollection.size()) of the vector to access

Returns:

the vector from 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 void search(Vec query,
                   double range,
                   java.util.List<java.lang.Integer> neighbors,
                   java.util.List<java.lang.Double> distances)

Description copied from interface: VectorCollection

Performs a range search of the current collection. The index and distance of each found neighbor will be placed into the given Lists.

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the point to search for the neighbors within a given radius.

range - the radius to search for all the neighbors with a distance ≤ range.

neighbors - the list to store the index of the neighbors in. Will be sorted by distance to the query, and paired with the values in distances.

distances - the list to store the distance of the neighbors to the query in. Will be sorted, and paired with the values in neighbors.

search

public void search(Vec query,
                   int numNeighbors,
                   java.util.List<java.lang.Integer> neighbors,
                   java.util.List<java.lang.Double> distances)

Description copied from interface: VectorCollection

Performs k-Nearest Neighbor search of the current collection. The index and distance of each found neighbor will be placed into the given Lists.

Specified by:

search in interface DualTree<V extends Vec>

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the point to search for the k-nearest neighbors of

numNeighbors - the number of neighbors k to search for.

neighbors - the list to store the index of the neighbors in. Will be sorted by distance to the query, and paired with the values in distances.

distances - the list to store the distance of the neighbors to the query in. Will be sorted, and paired with the values in neighbors.

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 DualTree<V extends Vec>

Specified by:

clone in interface IncrementalCollection<V extends Vec>

Specified by:

clone in interface VectorCollection<V extends Vec>

Overrides:

clone in class java.lang.Object

getAccelerationCache

public java.util.List<java.lang.Double> getAccelerationCache()

Specified by:

getAccelerationCache in interface VectorCollection<V extends Vec>