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
All Methods Instance Methods Abstract Methods Concrete Methods 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
-
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
-
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 relationdistance
- Distance functionexpansion
- Expansion ratetruncate
- 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 referenceb
- Object reference- Returns:
- Distance
-
distance
protected double distance(O a, DBIDRef b)
Compute a distance (and count).- Parameters:
a
- Object referenceb
- Object reference- Returns:
- Distance
-
excludeNotCovered
protected void excludeNotCovered(ModifiableDoubleDBIDList candidates, double fmax, ModifiableDoubleDBIDList collect)
Retain all elements within the current cover.- Parameters:
candidates
- Candidatesfmax
- Maximum distancecollect
- 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 objectcandidates
- Candidate listfmax
- Maximum distancecollect
- 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 interfaceIndex
-
getLogger
protected abstract Logging getLogger()
Get the class logger.- Returns:
- Logger
-
-