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>
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^{12} 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
 Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. ICML 2006.
 See Also:

Constructor Summary
ConstructorDescriptionConstructor.Constructor.Constructor.Constructor. 
Method Summary
Modifier and TypeMethodDescriptionstatic <T> CoverTree
<T, T> Return a cover tree of the data.static <T> CoverTree
<T, T> Return a cover tree of the data.static <T> CoverTree
<T, T> Return a cover tree of the data.static <T> CoverTree
<T, T> Return a cover tree of the data.void
Retrieves the neighbors in a fixed radius of query object, i.e.Retrieves the k nearest neighbors to the query key.toString()

Constructor Details

CoverTree
Constructor. Parameters:
keys
 the data keys.data
 the data objects.distance
 a metric distance measure for nearest neighbor search.

CoverTree
Constructor. Parameters:
keys
 the data keys.data
 the data objects.distance
 a metric distance measure for nearest neighbor search.

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

search
Description copied from interface:KNNSearch
Retrieves the k nearest neighbors to the query key. 
search
Description copied from interface:RNNSearch
Retrieves the neighbors in a fixed radius of query object, i.e.d(q, v) <= radius
.
