O
- Vector type@Reference(authors="J. L. Bentley", title="Multidimensional binary search trees used for associative searching", booktitle="Communications of the ACM, Vol. 18 Issue 9, Sept. 1975", url="http://dx.doi.org/10.1145/361002.361007") public class MinimalisticMemoryKDTree<O extends NumberVector> extends AbstractIndex<O> implements KNNIndex<O>, RangeIndex<O>
ArrayModifiableDBIDs
to sort the data in a
serialized tree.
Reference:
J. L. Bentley
Multidimensional binary search trees used for associative searching
Communications of the ACM, Vol. 18 Issue 9, Sept. 1975
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.
TODO: add support for weighted Minkowski distances.Modifier and Type | Class and Description |
---|---|
private static class |
MinimalisticMemoryKDTree.CountSortAccesses
Class to count object accesses during construnction.
|
static class |
MinimalisticMemoryKDTree.Factory<O extends NumberVector>
Factory class
|
class |
MinimalisticMemoryKDTree.KDTreeKNNQuery
kNN query for the k-d-tree.
|
class |
MinimalisticMemoryKDTree.KDTreeRangeQuery
kNN query for the k-d-tree.
|
Modifier and Type | Field and Description |
---|---|
(package private) int |
dims
The number of dimensions.
|
(package private) Counter |
distcalc
Counter for distance computations.
|
(package private) int |
leafsize
Maximum size of leaf nodes.
|
private static Logging |
LOG
Class logger
|
(package private) Counter |
objaccess
Counter for comparisons.
|
(package private) ArrayModifiableDBIDs |
sorted
The actual "tree" as a sorted array.
|
relation
Constructor and Description |
---|
MinimalisticMemoryKDTree(Relation<O> relation,
int leafsize)
Constructor.
|
Modifier and Type | Method and 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.
|
KNNQuery<O> |
getKNNQuery(DistanceQuery<O> distanceQuery,
Object... hints)
Get a KNN query object for the given distance query and k.
|
String |
getLongName()
A "pretty" name for the result, for use in titles, captions and menus.
|
RangeQuery<O> |
getRangeQuery(DistanceQuery<O> distanceQuery,
Object... hints)
Get a range query object for the given distance query and k.
|
String |
getShortName()
A short name for the result, useful for file names.
|
void |
initialize()
Initialize the index.
|
void |
logStatistics()
Send statistics to the logger, if enabled.
|
private static final Logging LOG
ArrayModifiableDBIDs sorted
int dims
int leafsize
final Counter objaccess
final Counter distcalc
public void initialize()
Index
initialize
in interface Index
private void buildTree(int left, int right, int axis, VectorUtil.SortDBIDsBySingleDimension comp)
left
- Interval minimumright
- Interval maximumaxis
- Current splitting axiscomp
- Comparatorpublic String getLongName()
Result
getLongName
in interface Result
getLongName
in class AbstractIndex<O extends NumberVector>
public String getShortName()
Result
getShortName
in interface Result
getShortName
in class AbstractIndex<O extends NumberVector>
public void logStatistics()
Index
logStatistics
in interface Index
protected void countObjectAccess()
protected void countDistanceComputation()
public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints)
KNNIndex
getKNNQuery
in interface KNNIndex<O extends NumberVector>
distanceQuery
- Distance queryhints
- Hints for the optimizernull
public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints)
RangeIndex
getRangeQuery
in interface RangeIndex<O extends NumberVector>
distanceQuery
- Distance queryhints
- Hints for the optimizernull
Copyright © 2015 ELKI Development Team, Lehr- und Forschungseinheit für Datenbanksysteme, Ludwig-Maximilians-Universität München. License information.