Class SimplifiedCoverTree<O>
- java.lang.Object
-
- elki.index.tree.metrical.covertree.AbstractCoverTree<O>
-
- elki.index.tree.metrical.covertree.SimplifiedCoverTree<O>
-
- All Implemented Interfaces:
DistancePriorityIndex<O>
,Index
,KNNIndex<O>
,RangeIndex<O>
public class SimplifiedCoverTree<O> extends AbstractCoverTree<O> implements DistancePriorityIndex<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 Int. Conf. Machine Learning (ICML 2006)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
SimplifiedCoverTree.CoverTreeKNNDBIDSearcher
KNN Query class.class
SimplifiedCoverTree.CoverTreeKNNObjectSearcher
KNN Query class.class
SimplifiedCoverTree.CoverTreeKNNSearcher
KNN Query class.class
SimplifiedCoverTree.CoverTreePriorityDBIDSearcher
Priority query class.class
SimplifiedCoverTree.CoverTreePriorityObjectSearcher
Priority query class.class
SimplifiedCoverTree.CoverTreePrioritySearcher<Q>
Priority query class.class
SimplifiedCoverTree.CoverTreeRangeDBIDSearcher
Range query class.class
SimplifiedCoverTree.CoverTreeRangeObjectSearcher
Range query class.class
SimplifiedCoverTree.CoverTreeRangeSearcher
Range query class.static class
SimplifiedCoverTree.Factory<O>
Index factory.private static class
SimplifiedCoverTree.Node
Node object.
-
Field Summary
Fields Modifier and Type Field Description private static Logging
LOG
Class logger.private SimplifiedCoverTree.Node
root
Tree root.-
Fields inherited from class elki.index.tree.metrical.covertree.AbstractCoverTree
distance, distComputations, expansion, invLogExpansion, relation, scaleBottom, truncate
-
-
Constructor Summary
Constructors Constructor Description SimplifiedCoverTree(Relation<O> relation, Distance<? super O> distance, double expansion, int truncate)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.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 SimplifiedCoverTree.Node root
Tree root.
-
-
Constructor Detail
-
SimplifiedCoverTree
public SimplifiedCoverTree(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 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 objectmaxScale
- Maximum scaleelems
- 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 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
-
-