Package elki.index.tree.metrical.covertree

Class AbstractCoverTree<O>

java.lang.Object

elki.index.tree.metrical.covertree.AbstractCoverTree<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index

Direct Known Subclasses:

CoverTree, SimplifiedCoverTree

public abstract class AbstractCoverTree<O>
extends java.lang.Object
implements Index

Abstract base class for cover tree variants.

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor	Description
AbstractCoverTree(Relation<O> relation, Distance<? super O> distance, double expansion, int truncate)	Constructor.

Method Summary

Modifier and Type	Method	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.
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 elki.index.Index

initialize

Field Detail

relation

protected final Relation<O> relation

The representation we are bound to.

expansion

protected 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

protected final double invLogExpansion

Logarithm base.

scaleBottom

protected final int scaleBottom

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

distance

protected Distance<? super O> distance

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,
                         Distance<? super O> distance,
                         double expansion,
                         int truncate)

Constructor.

Parameters:

relation - Data relation

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

Specified by:

logStatistics in interface Index

getLogger

protected abstract Logging getLogger()

Get the class logger.

Returns:

Logger