de.lmu.ifi.dbs.elki.index.tree.metrical.covertree

Class CoverTree<O>

java.lang.Object

de.lmu.ifi.dbs.elki.index.AbstractIndex<O>

de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.AbstractCoverTree<O>

de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.CoverTree<O>

All Implemented Interfaces:

Index, KNNIndex<O>, RangeIndex<O>, Result

@Reference(authors="A. Beygelzimer, S. Kakade, J. Langford",
           title="Cover trees for nearest neighbor",
           booktitle="In Proc. 23rd International Conference on Machine Learning (ICML)",
           url="http://dx.doi.org/10.1145/1143844.1143857")
public class CoverTree<O>
extends AbstractCoverTree<O>
implements RangeIndex<O>, KNNIndex<O>

Cover tree data structure (in-memory). This is a metrical data structure that is similar to the M-tree, but not as balanced and disk-oriented. However, by not having these requirements it does not require the expensive splitting procedures of M-tree. Reference:

A. Beygelzimer, S. Kakade, J. Langford
Cover trees for nearest neighbor
In Proc. 23rd International Conference on Machine Learning (ICML).

This implementation uses metrical pruning, and keeps the distances to the parent nodes. It thus needs more than twice the memory of SimplifiedCoverTree, but computes fewer distances. TODO: allow insertions and removals, as in the original publication.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	CoverTree.CoverTreeKNNQuery KNN Query class.
class	CoverTree.CoverTreeRangeQuery Range query class.
static class	CoverTree.Factory<O> Index factory.
private static class	CoverTree.Node Node object.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static Logging	LOG Class logger.
private CoverTree.Node	root Tree root.

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.AbstractCoverTree

distanceFunction, distComputations, expansion, invLogExpansion, scaleBottom, truncate

Fields inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

relation

Constructor Summary

Constructors

Constructor and Description
CoverTree(Relation<O> relation, DistanceFunction<? super O> distanceFunction, double expansion, int truncate) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected CoverTree.Node	bulkConstruct(DBIDRef cur, int maxScale, double parentDist, ModifiableDoubleDBIDList elems) Bulk-load the cover tree.
void	bulkLoad(DBIDs ids) Bulk-load the index.
private void	checkCoverTree(CoverTree.Node cur, int[] counts, int depth) Collect some statistics on the tree.
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) Get a KNN query object for the given distance query and k.
protected Logging	getLogger() Get the class logger.
RangeQuery<O>	getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) Get a range query object for the given distance query and k.
void	initialize() Initialize the index.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.AbstractCoverTree

collectByCover, distance, distance, distToScale, excludeNotCovered, getLongName, getShortName, logStatistics, maxDistance, scaleToDist

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.index.Index

logStatistics

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

getLongName, getShortName

Field Detail

LOG

static final Logging LOG

Class logger.

root

private CoverTree.Node root

Tree root.

Constructor Detail

CoverTree

public CoverTree(Relation<O> relation,
         DistanceFunction<? super O> distanceFunction,
         double expansion,
         int truncate)

Constructor.

Parameters:

relation - data relation

distanceFunction - distance function

expansion - Expansion rate

truncate - Truncate branches with less than this number of instances.

Method Detail

initialize

public void initialize()

Description copied from interface: Index

Initialize the index. For static indexes, this is the moment the index is bulk loaded.

Specified by:

initialize in interface Index

bulkLoad

public void bulkLoad(DBIDs ids)

Bulk-load the index.

Parameters:

ids - IDs to load

bulkConstruct

protected CoverTree.Node bulkConstruct(DBIDRef cur,
                           int maxScale,
                           double parentDist,
                           ModifiableDoubleDBIDList elems)

Bulk-load the cover tree. This bulk-load is slightly simpler than the one used in the original cover-tree source: We do not look back into the "far" set of candidates.

Parameters:

cur - Current routing object

maxScale - Maximum scale

elems - Candidates

Returns:

Root node of subtree

checkCoverTree

private void checkCoverTree(CoverTree.Node cur,
                  int[] counts,
                  int depth)

Collect some statistics on the tree.

Parameters:

cur - Current node

counts - Counter set

depth - Current depth

getRangeQuery

public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery,
                          Object... hints)

Description copied from interface: RangeIndex

Get a range query object for the given distance query and k. This function MAY return null, when the given distance is not supported!

Specified by:

getRangeQuery in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery,
                      Object... hints)

Description copied from interface: KNNIndex

Get a KNN query object for the given distance query and k. This function MAY return null, when the given distance is not supported!

Specified by:

getKNNQuery in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getLogger

protected Logging getLogger()

Description copied from class: AbstractCoverTree

Get the class logger.

Specified by:

getLogger in class AbstractCoverTree<O>

Returns:

Logger