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

References

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

Author:

Haifeng Li

Constructor Summary

Constructors

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

Method Summary

Methods

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, List<Neighbor<E,E>> neighbors) Search the neighbors in the given radius of query object, i.e.
void	setIdenticalExcluded(boolean excluded) Set if exclude query object self from the neighborhood.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, 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 String toString()

Overrides:

toString in class Object

setIdenticalExcluded

public void 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,
         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.