Class CoverTree<O>
- java.lang.Object
-
- elki.index.tree.metrical.covertree.AbstractCoverTree<O>
-
- elki.index.tree.metrical.covertree.CoverTree<O>
-
- All Implemented Interfaces:
DistancePriorityIndex<O>
,Index
,KNNIndex<O>
,RangeIndex<O>
@Reference(authors="A. Beygelzimer, S. Kakade, J. Langford", title="Cover trees for nearest neighbor", booktitle="In Proc. 23rd Int. Conf. Machine Learning (ICML 2006)", url="https://doi.org/10.1145/1143844.1143857", bibkey="DBLP:conf/icml/BeygelzimerKL06") @Priority(200) public class CoverTree<O> extends AbstractCoverTree<O> implements DistancePriorityIndex<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.This implementation contains some optimizations for Java: for example nodes with no children are stored efficiently in the parent node. Sometimes this also comes at some cost, as we currently do not push these onto a heap, but rather process them along with the parent node. This may cause additional distance computations (in particular for k nearest neighbor search), but also saves some overhead in managing these candidates.
Reference:
A. Beygelzimer, S. Kakade, J. Langford
Cover trees for nearest neighbor
In Proc. 23rd Int. Conf. Machine Learning (ICML 2006)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.
- Since:
- 0.7.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
CoverTree.CoverTreeKNNDBIDSearcher
KNN Query class.class
CoverTree.CoverTreeKNNObjectSearcher
KNN Query class.class
CoverTree.CoverTreeKNNSearcher
KNN Query class.class
CoverTree.CoverTreePriorityDBIDSearcher
Priority query class.class
CoverTree.CoverTreePriorityObjectSearcher
Priority query class.class
CoverTree.CoverTreePrioritySearcher<Q>
Priority query class.class
CoverTree.CoverTreeRangeDBIDSearcher
Range query class.class
CoverTree.CoverTreeRangeObjectSearcher
Range query class.class
CoverTree.CoverTreeRangeSearcher
Range query class.static class
CoverTree.Factory<O>
Index factory.private static class
CoverTree.Node
Node object.
-
Field Summary
Fields Modifier and Type Field Description private static Logging
LOG
Class logger.private CoverTree.Node
root
Tree root.-
Fields inherited from class elki.index.tree.metrical.covertree.AbstractCoverTree
distance, distComputations, expansion, invLogExpansion, relation, scaleBottom, truncate
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.protected Logging
getLogger()
Get the class logger.void
initialize()
Initialize the index.KNNSearcher<DBIDRef>
kNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a KNN query object for the given distance query and k.KNNSearcher<O>
kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a KNN query object for the given distance query and k.PrioritySearcher<DBIDRef>
priorityByDBID(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a priority search object.PrioritySearcher<O>
priorityByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a priority search object.RangeSearcher<DBIDRef>
rangeByDBID(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a range query object for the given distance query and k.RangeSearcher<O>
rangeByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a range query object for the given distance query and k.-
Methods inherited from class elki.index.tree.metrical.covertree.AbstractCoverTree
collectByCover, distance, distance, distToScale, excludeNotCovered, 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 elki.index.Index
logStatistics
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Class logger.
-
root
private CoverTree.Node root
Tree root.
-
-
Constructor Detail
-
CoverTree
public CoverTree(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
-
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 interfaceIndex
-
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 objectmaxScale
- Maximum scaleparentDist
- Distance to parent elementelems
- 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 nodecounts
- Counter setdepth
- Current depth
-
rangeByObject
public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
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:
rangeByObject
in interfaceDistancePriorityIndex<O>
- Specified by:
rangeByObject
in interfaceRangeIndex<O>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum rangeflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
rangeByDBID
public RangeSearcher<DBIDRef> rangeByDBID(DistanceQuery<O> distanceQuery, double maxradius, int flags)
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:
rangeByDBID
in interfaceRangeIndex<O>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum rangeflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
kNNByObject
public KNNSearcher<O> kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
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:
kNNByObject
in interfaceDistancePriorityIndex<O>
- Specified by:
kNNByObject
in interfaceKNNIndex<O>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum value of kflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
kNNByDBID
public KNNSearcher<DBIDRef> kNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)
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!
-
priorityByObject
public PrioritySearcher<O> priorityByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Description copied from interface:DistancePriorityIndex
Get a priority search object.- Specified by:
priorityByObject
in interfaceDistancePriorityIndex<O>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum search range (may beDouble.POSITIVE_INFINITY
flags
- Optimizer hints- Returns:
- Priority searcher
-
priorityByDBID
public PrioritySearcher<DBIDRef> priorityByDBID(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Description copied from interface:DistancePriorityIndex
Get a priority search object.- Specified by:
priorityByDBID
in interfaceDistancePriorityIndex<O>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum search range (may beDouble.POSITIVE_INFINITY
flags
- Optimizer hints- Returns:
- Priority searcher
-
getLogger
protected Logging getLogger()
Description copied from class:AbstractCoverTree
Get the class logger.- Specified by:
getLogger
in classAbstractCoverTree<O>
- Returns:
- Logger
-
-