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:

Serializable, Cloneable, VectorCollection<V>

public class KDTree<V extends Vec>
extends Object
implements VectorCollection<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).

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KDTree.KDTreeFactory<V extends Vec>
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() no-arg constructor for serialization
KDTree(List<V> vecs, DistanceMetric distanceMetric) Creates a new KDTree with the given data and methods.
KDTree(List<V> vecs, DistanceMetric distanceMetric, KDTree.PivotSelection pvSelection) Creates a new KDTree with the given data and methods.
KDTree(List<V> vecs, DistanceMetric distanceMetric, KDTree.PivotSelection pvSelection, ExecutorService threadpool) Creates a new KDTree with the given data and methods.

Method Summary

Modifier and Type	Method and Description
KDTree<V>	clone()
int	getSplitIndex(List<Integer> data, int pivot)
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
int	size() Returns the number of vectors stored in the collection

Methods inherited from class java.lang.Object

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

Constructor Detail

KDTree

public KDTree(List<V> vecs,
              DistanceMetric distanceMetric,
              KDTree.PivotSelection pvSelection,
              ExecutorService threadpool)

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.

threadpool - the source of threads to use when constructing. Null is permitted, in which case a serial construction will occur.

KDTree

public KDTree(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(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()

no-arg constructor for serialization

Method Detail

getSplitIndex

public int getSplitIndex(List<Integer> data,
                         int pivot)

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

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

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.

clone

public KDTree<V> clone()

Specified by:

clone in interface VectorCollection<V extends Vec>

Overrides:

clone in class Object