Package elki.index.tree.spatial.kd
Class MemoryKDTree<O extends NumberVector>
- java.lang.Object
-
- elki.index.tree.spatial.kd.MemoryKDTree<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") public class MemoryKDTree<O extends NumberVector> extends java.lang.Object implements DistancePriorityIndex<O>
Implementation of a static in-memory K-D-tree.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 private class
MemoryKDTree.CountingRelation
Proxy to count accesses.static class
MemoryKDTree.Factory<O extends NumberVector>
Factory classstatic class
MemoryKDTree.KDNode
KD tree node.class
MemoryKDTree.KDTreeKNNSearcher
kNN query for the k-d-tree.class
MemoryKDTree.KDTreePrioritySearcher
Priority search for the k-d-tree.class
MemoryKDTree.KDTreeRangeSearcher
Range query for the k-d-tree.private static class
MemoryKDTree.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 java.lang.Object
root
Root node (KDNode or IntIntPair)protected ArrayDBIDs
sorted
The actual "tree" as a sorted array.protected SplitStrategy
split
Split stragegy
-
Constructor Summary
Constructors Constructor Description MemoryKDTree(Relation<O> relation, int leafsize)
Constructor with default split (used by EmpiricalQueryOptimizer).MemoryKDTree(Relation<O> relation, SplitStrategy split, int leafsize)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private boolean
assertSplitConsistent(int left, int pos, int right, int dim, double val, DBIDArrayMIter iter)
Assert that the generated split is consistent.java.lang.Object
buildTree(Relation<? extends NumberVector> relation, int left, int right, ArrayModifiableDBIDs sorted, DBIDArrayMIter iter, VectorUtil.SortDBIDsBySingleDimension comp)
Build the k-d tree.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.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.
-
split
protected SplitStrategy split
Split stragegy
-
leafsize
protected int leafsize
Maximum size of leaf nodes.
-
sorted
protected ArrayDBIDs sorted
The actual "tree" as a sorted array.
-
root
protected java.lang.Object root
Root node (KDNode or IntIntPair)
-
dims
protected int dims
The number of dimensions.
-
objaccess
protected final Counter objaccess
Counter for comparisons.
-
distcalc
protected final Counter distcalc
Counter for distance computations.
-
-
Constructor Detail
-
MemoryKDTree
public MemoryKDTree(Relation<O> relation, int leafsize)
Constructor with default split (used by EmpiricalQueryOptimizer).- Parameters:
relation
- Relation to indexleafsize
- Leaf size
-
MemoryKDTree
public MemoryKDTree(Relation<O> relation, SplitStrategy split, int leafsize)
Constructor.- Parameters:
relation
- Relation to indexsplit
- Split strategyleafsize
- Maximum size of leaf nodes
-
-
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
public java.lang.Object buildTree(Relation<? extends NumberVector> relation, int left, int right, ArrayModifiableDBIDs sorted, DBIDArrayMIter iter, VectorUtil.SortDBIDsBySingleDimension comp)
Build the k-d tree.- Parameters:
relation
- Relationleft
- interval startright
- interval endsorted
- object idsiter
- iterator on the idscomp
- comparator on the values- Returns:
- root node
-
assertSplitConsistent
private boolean assertSplitConsistent(int left, int pos, int right, int dim, double val, DBIDArrayMIter iter)
Assert that the generated split is consistent.- Parameters:
left
- Interval startpos
- Split positionright
- Interval enddim
- Split dimensionval
- Split thresholditer
- Iterator
-
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
-
-