smile.neighbor

Class CoverTree<E>

java.lang.Object

smile.neighbor.CoverTree<E>

Type Parameters:

E - the type of data objects in the tree.

All Implemented Interfaces:

KNNSearch<E,E>, NearestNeighborSearch<E,E>, RNNSearch<E,E>

public class CoverTree<E>
extends java.lang.Object
implements NearestNeighborSearch<E,E>, KNNSearch<E,E>, RNNSearch<E,E>

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 read from secondary storage in production.

References

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

Constructor Summary

Constructors

Constructor and Description
CoverTree(E[] dataset, Metric<E> distance) Constructor.
CoverTree(E[] dataset, Metric<E> distance, double base) Constructor.

Method Summary

Modifier and Type	Method and Description
boolean	isIdenticalExcluded() Get whether if query object self be excluded from the neighborhood.
Neighbor<E,E>[]	knn(E q, int k) Search the k nearest neighbors to the query.
Neighbor<E,E>	nearest(E q) Search the nearest neighbor to the given sample.
void	range(E q, double radius, java.util.List<Neighbor<E,E>> neighbors) Search the neighbors in the given radius of query object, i.e.
CoverTree<E>	setIdenticalExcluded(boolean excluded) Set if exclude query object self from the neighborhood.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

CoverTree

public CoverTree(E[] dataset,
                 Metric<E> distance)

Constructor.

Parameters:

dataset - the data set for nearest neighbor search.

distance - a metric distance measure for nearest neighbor search.

CoverTree

public CoverTree(E[] dataset,
                 Metric<E> distance,
                 double base)

Constructor.

Parameters:

dataset - the data set for nearest neighbor search.

distance - a metric distance measure for nearest neighbor search.

base - the base of the expansion constant.

Method Detail

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

setIdenticalExcluded

public CoverTree<E> setIdenticalExcluded(boolean excluded)

Set if exclude query object self from the neighborhood.

isIdenticalExcluded

public boolean isIdenticalExcluded()

Get whether if query object self be excluded from the neighborhood.

nearest

public Neighbor<E,E> nearest(E q)

Description copied from interface: NearestNeighborSearch

Search the nearest neighbor to the given sample.

Specified by:

nearest in interface NearestNeighborSearch<E,E>

Parameters:

q - the query key.

Returns:

the nearest neighbor

knn

public Neighbor<E,E>[] knn(E q,
                           int k)

Description copied from interface: KNNSearch

Search the k nearest neighbors to the query.

Specified by:

knn in interface KNNSearch<E,E>

Parameters:

q - the query key.

k - the number of nearest neighbors to search for.

range

public void range(E q,
                  double radius,
                  java.util.List<Neighbor<E,E>> neighbors)

Description copied from interface: RNNSearch

Search the neighbors in the given radius of query object, i.e. d(q, v) ≤ radius.

Specified by:

range in interface RNNSearch<E,E>

Parameters:

q - the query key.

radius - the radius of search range from target.

neighbors - the list to store found neighbors in the given range on output.