Class MinimalisticMemoryKDTree<O extends NumberVector>
- java.lang.Object
-
- elki.index.tree.spatial.kd.MinimalisticMemoryKDTree<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 MinimalisticMemoryKDTree<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 oneArrayModifiableDBIDs
to sort the data in a serialized tree.Reference:
J. L. Bentley
Multidimensional binary search trees used for associative searching
Communications of the ACM 18(9)The version
SmallMemoryKDTree
uses 3x more memory, but is considerably faster because it keeps a local copy of the attribute values, thus reducing the number of accesses to the relation substantially. In particular, this reduces construction time.MemoryKDTree
needs even more memory, but uses much better splits and hence is usually the best choice.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.6.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
MinimalisticMemoryKDTree.CountSortAccesses
Class to count object accesses during construction.static class
MinimalisticMemoryKDTree.Factory<O extends NumberVector>
Factory classclass
MinimalisticMemoryKDTree.KDTreeKNNSearcher
kNN query for the k-d-tree.class
MinimalisticMemoryKDTree.KDTreePrioritySearcher
Priority search for the k-d-tree.class
MinimalisticMemoryKDTree.KDTreeRangeSearcher
Range query for the k-d-tree.private static class
MinimalisticMemoryKDTree.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 ArrayModifiableDBIDs
sorted
The actual "tree" as a sorted array.
-
Constructor Summary
Constructors Constructor Description MinimalisticMemoryKDTree(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, VectorUtil.SortDBIDsBySingleDimension comp)
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 maxradius, 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 ArrayModifiableDBIDs 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, VectorUtil.SortDBIDsBySingleDimension comp)
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 axiscomp
- Comparator
-
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 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 extends NumberVector>
- Specified by:
rangeByObject
in interfaceRangeIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxradius
- 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
-
-