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.Modifier and Type | Class and Description |
---|---|
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.
|
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)
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.
|
<D extends Distance<D>> |
getKNNQuery(DistanceQuery<O,D> 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.
|
<D extends Distance<D>> |
getRangeQuery(DistanceQuery<O,D> 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
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 <D extends Distance<D>> KNNQuery<O,D> getKNNQuery(DistanceQuery<O,D> distanceQuery, Object... hints)
KNNIndex
getKNNQuery
in interface KNNIndex<O extends NumberVector<?>>
D
- Distance typedistanceQuery
- Distance queryhints
- Hints for the optimizernull
public <D extends Distance<D>> RangeQuery<O,D> getRangeQuery(DistanceQuery<O,D> distanceQuery, Object... hints)
RangeIndex
getRangeQuery
in interface RangeIndex<O extends NumberVector<?>>
D
- Distance typedistanceQuery
- Distance queryhints
- Hints for the optimizernull