Package smile.neighbor

Class CoverTree<K,V>

java.lang.Object

smile.neighbor.CoverTree<K,V>

Type Parameters:

K - the type of keys.

V - the type of associated objects.

All Implemented Interfaces:

Serializable, KNNSearch<K,V>, RNNSearch<K,V>

public class CoverTree<K,V>
extends Object
implements KNNSearch<K,V>, RNNSearch<K,V>, Serializable

Cover tree is a data structure for generic nearest neighbor search, which is especially efficient in spaces with small intrinsic dimension. The cover tree has a theoretical bound that is based on the dataset's doubling constant. The bound on search time is O(c¹² log node) where c is the expansion constant of the dataset.

By default, the query object (reference equality) is excluded from the neighborhood. You may change this behavior with setIdenticalExcluded. Note that you may observe weird behavior with String objects. JVM will pool the string literal objects. So the below variables String a = "ABC"; String b = "ABC"; String c = "AB" + "C"; are actually equal in reference test a == b == c. With toy data that you type explicitly in the code, this will cause problems. Fortunately, the data would be generally read from secondary storage in production.

References

1. Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. ICML 2006.

See Also:

• Serialized Form

Constructor Summary

Constructors

Constructor	Description
CoverTree(List<K> keys, List<V> data, Metric<K> distance)	Constructor.
CoverTree(List<K> keys, List<V> data, Metric<K> distance, double base)	Constructor.
CoverTree(K[] keys, V[] data, Metric<K> distance)	Constructor.
CoverTree(K[] keys, V[] data, Metric<K> distance, double base)	Constructor.

Method Summary

Modifier and Type	Method	Description
static <T> CoverTree<T,T>	of(List<T> data, Metric<T> distance)	Return a cover tree of the data.
static <T> CoverTree<T,T>	of(List<T> data, Metric<T> distance, double base)	Return a cover tree of the data.
static <T> CoverTree<T,T>	of(T[] data, Metric<T> distance)	Return a cover tree of the data.
static <T> CoverTree<T,T>	of(T[] data, Metric<T> distance, double base)	Return a cover tree of the data.
void	search(K q, double radius, List<Neighbor<K,V>> neighbors)	Retrieves the neighbors in a fixed radius of query object, i.e.
Neighbor<K,V>[]	search(K q, int k)	Retrieves the k nearest neighbors to the query key.
String	toString()

Methods inherited from class java.lang.Object

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

Methods inherited from interface smile.neighbor.KNNSearch

nearest

Constructor Details

CoverTree

public CoverTree(K[] keys,
 V[] data,
 Metric<K> distance)

Constructor.

Parameters:

keys - the data keys.

data - the data objects.

distance - a metric distance measure for nearest neighbor search.

CoverTree

public CoverTree(List<K> keys,
 List<V> data,
 Metric<K> distance)

Constructor.

Parameters:

keys - the data keys.

data - the data objects.

distance - a metric distance measure for nearest neighbor search.

CoverTree

public CoverTree(K[] keys,
 V[] data,
 Metric<K> distance,
 double base)

Constructor.

Parameters:

keys - the data keys.

data - the data objects.

distance - a metric distance measure for nearest neighbor search.

base - the base of the expansion constant.

CoverTree

public CoverTree(List<K> keys,
 List<V> data,
 Metric<K> distance,
 double base)

Constructor.

Parameters:

keys - the data keys.

data - the data objects.

distance - a metric distance measure for nearest neighbor search.

base - the base of the expansion constant.

Method Details

of

public static <T> CoverTree<T,T> of(T[] data,
 Metric<T> distance)

Return a cover tree of the data.

Type Parameters:

T - the type of keys and values.

Parameters:

data - the data objects, which are also used as key.

distance - a metric distance measure for nearest neighbor search.

Returns:

Cover tree.

of

public static <T> CoverTree<T,T> of(T[] data,
 Metric<T> distance,
 double base)

Return a cover tree of the data.

Type Parameters:

T - the type of keys and values.

Parameters:

data - the data objects, which are also used as key.

distance - a metric distance measure for nearest neighbor search.

base - the base of the expansion constant.

Returns:

Cover tree.

of

public static <T> CoverTree<T,T> of(List<T> data,
 Metric<T> distance)

Return a cover tree of the data.

Type Parameters:

T - the type of keys and values.

Parameters:

data - the data objects, which are also used as key.

distance - a metric distance measure for nearest neighbor search.

Returns:

Cover tree.

of

public static <T> CoverTree<T,T> of(List<T> data,
 Metric<T> distance,
 double base)

Return a cover tree of the data.

Type Parameters:

T - the type of keys and values.

Parameters:

data - the data objects, which are also used as key.

distance - a metric distance measure for nearest neighbor search.

base - the base of the expansion constant.

Returns:

Cover tree.

toString

public String toString()

Overrides:

toString in class Object

search

public Neighbor<K,V>[] search(K q,
 int k)

Description copied from interface: KNNSearch

Retrieves the k nearest neighbors to the query key.

Specified by:

search in interface KNNSearch<K,V>

Parameters:

q - the query key.

k - the number of nearest neighbors to search for.

Returns:

the k nearest neighbors

search

public void search(K q,
 double radius,
 List<Neighbor<K,V>> neighbors)

Description copied from interface: RNNSearch

Retrieves the neighbors in a fixed radius of query object, i.e. d(q, v) <= radius.

Specified by:

search in interface RNNSearch<K,V>

Parameters:

q - the query key.

radius - the radius of search range from target.

neighbors - the list to store found neighbors on output.