Class SmallMemoryKDTree<O extends NumberVector>
- java.lang.Object
-
- elki.index.tree.spatial.kd.SmallMemoryKDTree<O>
-
- Type Parameters:
O
- Vector type
- All Implemented Interfaces:
DistancePriorityIndex<O>
,Index
,KNNIndex<O>
,RangeIndex<O>
@Reference(authors="J. L. Bentley", title="Multidimensional binary search trees used for associative searching", booktitle="Communications of the ACM 18(9)", url="https://doi.org/10.1145/361002.361007", bibkey="DBLP:journals/cacm/Bentley75") @Priority(-101) public class SmallMemoryKDTree<O extends NumberVector> extends java.lang.Object implements DistancePriorityIndex<O>
Simple implementation of a static in-memory K-D-tree. Does not support dynamic updates or anything, but also is very simple and memory efficient: all it uses is oneModifiableDoubleDBIDList
to sort the data in a serialized tree and store the current attribute value.It needs about 3 times as much memory as
MinimalisticMemoryKDTree
but it is also considerably faster because it does not need to lookup this value from the vectors.MemoryKDTree
needs even more memory, but uses much better splits and hence is usually the best choice.Reference:
J. L. Bentley
Multidimensional binary search trees used for associative searching
Communications of the ACM 18(9)The search uses an improved search strategy published by:
S. Arya and D. M. Mount
Algorithms for fast vector quantization
Proc. DCC '93: Data Compression ConferenceTODO: add support for weighted Minkowski distances.
- Since:
- 0.7.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
SmallMemoryKDTree.Factory<O extends NumberVector>
Factory classclass
SmallMemoryKDTree.KDTreeKNNSearcher
kNN query for the k-d-tree.class
SmallMemoryKDTree.KDTreePrioritySearcher
Priority search for the k-d-tree.class
SmallMemoryKDTree.KDTreeRangeSearcher
Range query for the k-d-tree.private static class
SmallMemoryKDTree.PrioritySearchBranch
Search position for priority search.
-
Field Summary
Fields Modifier and Type Field Description protected int
dims
The number of dimensions.protected Counter
distcalc
Counter for distance computations.protected int
leafsize
Maximum size of leaf nodes.private static Logging
LOG
Class loggerprotected Counter
objaccess
Counter for comparisons.protected Relation<O>
relation
The representation we are bound to.protected ModifiableDoubleDBIDList
sorted
The actual "tree" as a sorted array.
-
Constructor Summary
Constructors Constructor Description SmallMemoryKDTree(Relation<O> relation, int leafsize)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
buildTree(int left, int right, int axis, DoubleDBIDListMIter iter)
Recursively build the tree by partial sorting.protected void
countDistanceComputation()
Count a distance computation.protected void
countObjectAccess()
Count a single object access.void
initialize()
Initialize the index.KNNSearcher<O>
kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a KNN query object for the given distance query and k.void
logStatistics()
Send statistics to the logger, if enabled.private int
next(int axis)
Next axis.PrioritySearcher<O>
priorityByObject(DistanceQuery<O> distanceQuery, double maxrange, int flags)
Get a priority search object.RangeSearcher<O>
rangeByObject(DistanceQuery<O> distanceQuery, double maxrange, int flags)
Get a range query object for the given distance query and k.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.index.DistancePriorityIndex
priorityByDBID
-
Methods inherited from interface elki.index.RangeIndex
rangeByDBID
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Class logger
-
relation
protected final Relation<O extends NumberVector> relation
The representation we are bound to.
-
sorted
protected ModifiableDoubleDBIDList sorted
The actual "tree" as a sorted array.
-
dims
protected int dims
The number of dimensions.
-
leafsize
protected int leafsize
Maximum size of leaf nodes.
-
objaccess
protected final Counter objaccess
Counter for comparisons.
-
distcalc
protected final Counter distcalc
Counter for distance computations.
-
-
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
-
buildTree
private void buildTree(int left, int right, int axis, DoubleDBIDListMIter iter)
Recursively build the tree by partial sorting. O(n log n) complexity. Apparently there exists a variant in only O(n log log n)? Please contribute!- Parameters:
left
- Interval minimumright
- Interval maximumaxis
- Current splitting axisiter
- Iterator
-
next
private int next(int axis)
Next axis.- Parameters:
axis
- Current axis- Returns:
- Next axis
-
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
-
countObjectAccess
protected void countObjectAccess()
Count a single object access.
-
countDistanceComputation
protected void countDistanceComputation()
Count a distance computation.
-
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 extends NumberVector>
- Specified by:
kNNByObject
in interfaceKNNIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum value of kflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
rangeByObject
public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery, double maxrange, 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 extends NumberVector>
- Specified by:
rangeByObject
in interfaceRangeIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxrange
- Maximum rangeflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
priorityByObject
public PrioritySearcher<O> priorityByObject(DistanceQuery<O> distanceQuery, double maxrange, int flags)
Description copied from interface:DistancePriorityIndex
Get a priority search object.- Specified by:
priorityByObject
in interfaceDistancePriorityIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxrange
- Maximum search range (may beDouble.POSITIVE_INFINITY
flags
- Optimizer hints- Returns:
- Priority searcher
-
-