jsat.linear.vectorcollection

Class KDTree<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.KDTree<V>

Type Parameters:

V - The vector type

All Implemented Interfaces:

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

public class KDTree<V extends Vec>
extends java.lang.Object
implements IncrementalCollection<V>

Standard KDTree implementation. KDTrees are fast to create with no distance computations needed. Though KDTrees can be constructed in O(n) time, this implementation is O(n log n). KDTrees can be very fast for low dimensional data queries, but degrade as the dimensions increases. For very high dimensions or pathologically bad data, O(n²) performance worse then VectorArray can occur.

Note: KD trees are only usable with Distance Metrics based off of the pNorm between two vectors. The valid distance metrics are EuclideanDistance, ChebyshevDistance, ManhattanDistance, MinkowskiDistance

See:

• Bentley, J. L. (1975). Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM, 18(9), 509–517. http://doi.org/10.1145/361002.361007
• Moore, A. (1991). A tutorial on kd-trees (No. Technical Report No. 209).

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KDTree.PivotSelection KDTree uses an index of the vector at each stage to use as a pivot, dividing the remaining elements into two sets.

Constructor Summary

Constructors

Constructor and Description
KDTree()
KDTree(KDTree.PivotSelection pivotSelection)
KDTree(java.util.List<V> vecs, DistanceMetric distanceMetric) Creates a new KDTree with the given data and methods.
KDTree(java.util.List<V> vecs, DistanceMetric distanceMetric, KDTree.PivotSelection pvSelection) Creates a new KDTree with the given data and methods.
KDTree(java.util.List<V> vecs, DistanceMetric distanceMetric, KDTree.PivotSelection pvSelection, boolean parallel) Creates a new KDTree with the given data and methods.

Method Summary

Modifier and Type	Method and Description
void	build(boolean parallel, java.util.List<V> vecs, DistanceMetric dm) Builds this metric index from the given collection of points using the given distance metric.
KDTree<V>	clone()
V	get(int indx) Accesses a vector from this collection via index.
java.util.List<java.lang.Double>	getAccelerationCache()
DistanceMetric	getDistanceMetric()
int	getLeafSize()
int	getMedianIndex(java.util.List<java.lang.Integer> data, int pivot) Returns the index for the median, adjusted incase multiple features have the same value.
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	setLeafSize(int leaf_size) Sets the number of points stored within a leaf node of the index.
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.VectorCollection

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

Constructor Detail

KDTree

public KDTree(java.util.List<V> vecs,
              DistanceMetric distanceMetric,
              KDTree.PivotSelection pvSelection,
              boolean parallel)

Creates a new KDTree with the given data and methods.

Parameters:

vecs - the list of vectors to place in this structure

distanceMetric - the metric to use for the space

pvSelection - the method of selection to use for determining what pivot to use.

parallel - true if multiple threads should be used for construction, false otherwise.

KDTree

public KDTree(java.util.List<V> vecs,
              DistanceMetric distanceMetric,
              KDTree.PivotSelection pvSelection)

Creates a new KDTree with the given data and methods.

Parameters:

vecs - the list of vectors to place in this structure

distanceMetric - the metric to use for the space

pvSelection - the method of selection to use for determining what pivot to use.

KDTree

public KDTree(java.util.List<V> vecs,
              DistanceMetric distanceMetric)

Creates a new KDTree with the given data and methods.

Parameters:

vecs - the list of vectors to place in this structure

distanceMetric - the metric to use for the space

KDTree

public KDTree(KDTree.PivotSelection pivotSelection)

KDTree

public KDTree()

Method Detail

getAccelerationCache

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

Specified by:

getAccelerationCache in interface VectorCollection<V extends Vec>

setLeafSize

public void setLeafSize(int leaf_size)

Sets the number of points stored within a leaf node of the index. Larger values avoid search overhead, but reduce opportunities for pruning.

Parameters:

leaf_size - the size of a leaf node. Must be at least 2

getLeafSize

public int getLeafSize()

Returns:

the number of points to store within a leaf node

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

build

public void build(boolean parallel,
                  java.util.List<V> vecs,
                  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.

vecs - the list of vectors to put into the index

dm - the distance metric to build the index using.

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

getMedianIndex

public int getMedianIndex(java.util.List<java.lang.Integer> data,
                          int pivot)

Returns the index for the median, adjusted incase multiple features have the same value.

Parameters:

data - the dataset to get the median index of

pivot - the dimension to pivot on, and ensure the median index has a different value on the left side

Returns:

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

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

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.

clone

public KDTree<V> clone()

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