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

Class SimplifiedCoverTree<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.SimplifiedCoverTree<O>

All Implemented Interfaces:

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

@Priority(value=200)
public class SimplifiedCoverTree<O>
extends AbstractCoverTree<O>
implements RangeIndex<O>, KNNIndex<O>

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

This version does not store the distance to the parent, so it needs only about 40% of the memory of CoverTree but does more distance computations for search.

Reference:

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

TODO: allow insertions and removals, as in the original publication.

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Class logger.
private SimplifiedCoverTree.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
SimplifiedCoverTree(Relation<O> relation, DistanceFunction<? super O> distanceFunction, double expansion, int truncate) Constructor.

Method Summary

Modifier and Type	Method and Description
protected SimplifiedCoverTree.Node	bulkConstruct(DBIDRef cur, int maxScale, ModifiableDoubleDBIDList elems) Bulk-load the cover tree.
void	bulkLoad(DBIDs ids) Bulk-load the index.
private void	checkCoverTree(SimplifiedCoverTree.Node cur, int[] counts, int depth) Collect some statistics on the tree.
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, java.lang.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, java.lang.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

private static final Logging LOG

Class logger.

root

private SimplifiedCoverTree.Node root

Tree root.

Constructor Detail

SimplifiedCoverTree

public SimplifiedCoverTree(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 SimplifiedCoverTree.Node bulkConstruct(DBIDRef cur,
                                                 int maxScale,
                                                 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(SimplifiedCoverTree.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,
                                   java.lang.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,
                               java.lang.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