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

Class AbstractCoverTree<O>

java.lang.Object

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

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

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, Result

Direct Known Subclasses:

CoverTree, SimplifiedCoverTree

public abstract class AbstractCoverTree<O>
extends AbstractIndex<O>

Abstract base class for cover tree variants.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	AbstractCoverTree.Factory<O,I extends AbstractCoverTree<O>> Index factory.

Field Summary

Fields

Modifier and Type	Field and Description
protected DistanceFunction<? super O>	distanceFunction Holds the instance of the trees distance function.
private DistanceQuery<O>	distanceQuery Distance query, on the data relation.
protected long	distComputations Distance computations performed.
(package private) double	expansion Constant expansion rate. 2 would be the intuitive value, but the original version used 1.3, so we copy this.
(package private) double	invLogExpansion Logarithm base.
protected int	scaleBottom Remaining points are likely identical.
protected int	truncate Stop refining the tree at this size, but build a leaf.

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

relation

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and Description
protected void	collectByCover(DBIDRef cur, ModifiableDoubleDBIDList candidates, double fmax, ModifiableDoubleDBIDList collect) Collect all elements with respect to a new routing object.
protected double	distance(DBIDRef a, DBIDRef b) Compute a distance (and count).
protected double	distance(O a, DBIDRef b) Compute a distance (and count).
protected int	distToScale(double d) Convert a distance to an upper scaling bound-
protected void	excludeNotCovered(ModifiableDoubleDBIDList candidates, double fmax, ModifiableDoubleDBIDList collect) Retain all elements within the current cover.
protected abstract Logging	getLogger() Get the class logger.
String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
String	getShortName() A short name for the result, useful for file names.
void	logStatistics() Send statistics to the logger, if enabled.
protected double	maxDistance(DoubleDBIDList elems) Find maximum in a list via scanning.
protected double	scaleToDist(int s) Convert a scaling factor to a distance.

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

initialize

Field Detail

expansion

final double expansion

Constant expansion rate. 2 would be the intuitive value, but the original version used 1.3, so we copy this. This means that in every level, the cover radius shrinks by 1.3.

invLogExpansion

final double invLogExpansion

Logarithm base.

scaleBottom

protected final int scaleBottom

Remaining points are likely identical. For 1.3 this yields: -2700

distanceFunction

protected DistanceFunction<? super O> distanceFunction

Holds the instance of the trees distance function.

distanceQuery

private DistanceQuery<O> distanceQuery

Distance query, on the data relation.

distComputations

protected long distComputations

Distance computations performed.

truncate

protected int truncate

Stop refining the tree at this size, but build a leaf.

Constructor Detail

AbstractCoverTree

public AbstractCoverTree(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

scaleToDist

protected final double scaleToDist(int s)

Convert a scaling factor to a distance.

Parameters:

s - Scaling factor

Returns:

Distance

distToScale

protected final int distToScale(double d)

Convert a distance to an upper scaling bound-

Parameters:

d - Distance

Returns:

Scaling bound

maxDistance

protected double maxDistance(DoubleDBIDList elems)

Find maximum in a list via scanning.

Parameters:

elems - Elements

Returns:

Maximum distance

distance

protected double distance(DBIDRef a,
              DBIDRef b)

Compute a distance (and count).

Parameters:

a - Object reference

b - Object reference

Returns:

Distance

distance

protected double distance(O a,
              DBIDRef b)

Compute a distance (and count).

Parameters:

a - Object reference

b - Object reference

Returns:

Distance

excludeNotCovered

protected void excludeNotCovered(ModifiableDoubleDBIDList candidates,
                     double fmax,
                     ModifiableDoubleDBIDList collect)

Retain all elements within the current cover.

Parameters:

candidates - Candidates

fmax - Maximum distance

collect - Far neighbors

collectByCover

protected void collectByCover(DBIDRef cur,
                  ModifiableDoubleDBIDList candidates,
                  double fmax,
                  ModifiableDoubleDBIDList collect)

Collect all elements with respect to a new routing object.

Parameters:

cur - Routing object

candidates - Candidate list

fmax - Maximum distance

collect - Output list

logStatistics

public void logStatistics()

Description copied from interface: Index

Send statistics to the logger, if enabled. Note: you must have set the logging level appropriately before initializing the index! Otherwise, the index might not have collected the desired statistics.

getLogger

protected abstract Logging getLogger()

Get the class logger.

Returns:

Logger

getLongName

public String getLongName()

Description copied from interface: Result

A "pretty" name for the result, for use in titles, captions and menus.

Specified by:

getLongName in interface Result

Specified by:

getLongName in class AbstractIndex<O>

Returns:

result name

getShortName

public String getShortName()

Description copied from interface: Result

A short name for the result, useful for file names.

Specified by:

getShortName in interface Result

Specified by:

getShortName in class AbstractIndex<O>

Returns:

result name