jsat.linear.vectorcollection

Class CoverTree<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.CoverTree<V>

All Implemented Interfaces:

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

public final class CoverTree<V extends Vec>
extends Object
implements IncrementalCollection<V>

This class implements the Cover-tree algorithm for answering nearest neighbor queries. In particular, it uses the "Simplified Cover-tree" algorithm.
Note, this implementation does not yet support parallel construction.
See:

• Beygelzimer, A., Kakade, S., & Langford, J. (2006). Cover trees for nearest neighbor. In International Conference on Machine Learning (pp. 97–104). New York: ACM. Retrieved from here
• Izbicki, M., & Shelton, C. R. (2015). Faster Cover Trees. In Proceedings of the Thirty-Second International Conference on Machine Learning (Vol. 37).

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CoverTree.CoverTreeFactory<V extends Vec>

Constructor Summary

Constructors

Constructor and Description
CoverTree(CoverTree<V> toCopy)
CoverTree(DistanceMetric dm)
CoverTree(List<V> source, DistanceMetric dm)
CoverTree(List<V> source, DistanceMetric dm, ExecutorService threadpool)
CoverTree(List<V> source, DistanceMetric dm, ExecutorService threadpool, boolean looseBounds)

Method Summary

Modifier and Type	Method and Description
CoverTree<V>	clone()
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	setLooseBounds(boolean looseBounds)
protected jsat.linear.vectorcollection.CoverTree.TreeNode	simpleInsert_(jsat.linear.vectorcollection.CoverTree.TreeNode p, int x_indx) prerequisites: d(p,x) ≤ covdist(p)
protected jsat.linear.vectorcollection.CoverTree.TreeNode	simpleInsert(jsat.linear.vectorcollection.CoverTree.TreeNode p, int x_indx)
protected void	simpleInsert(V x)
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

CoverTree

public CoverTree(DistanceMetric dm)

CoverTree

public CoverTree(List<V> source,
                 DistanceMetric dm)

CoverTree

public CoverTree(List<V> source,
                 DistanceMetric dm,
                 ExecutorService threadpool)

CoverTree

public CoverTree(List<V> source,
                 DistanceMetric dm,
                 ExecutorService threadpool,
                 boolean looseBounds)

CoverTree

public CoverTree(CoverTree<V> toCopy)

Method Detail

setLooseBounds

public void setLooseBounds(boolean looseBounds)

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

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

clone

public CoverTree<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

simpleInsert

protected void simpleInsert(V x)

simpleInsert

protected jsat.linear.vectorcollection.CoverTree.TreeNode simpleInsert(jsat.linear.vectorcollection.CoverTree.TreeNode p,
                                                                       int x_indx)

simpleInsert_

protected jsat.linear.vectorcollection.CoverTree.TreeNode simpleInsert_(jsat.linear.vectorcollection.CoverTree.TreeNode p,
                                                                        int x_indx)

prerequisites: d(p,x) ≤ covdist(p)

Parameters:

p -

x_indx -

Returns:

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