de.lmu.ifi.dbs.elki.index.tree.spatial.kd

Class SmallMemoryKDTree<O extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.index.AbstractIndex<O>

de.lmu.ifi.dbs.elki.index.tree.spatial.kd.SmallMemoryKDTree<O>

Type Parameters:

O - Vector type

All Implemented Interfaces:

Index, KNNIndex<O>, RangeIndex<O>, Result

@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 SmallMemoryKDTree<O extends NumberVector>
extends AbstractIndex<O>
implements KNNIndex<O>, RangeIndex<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 one ModifiableDoubleDBIDList 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. Reference:

J. L. Bentley
Multidimensional binary search trees used for associative searching
Communications of the ACM, Vol. 18 Issue 9, Sept. 1975

TODO: add support for weighted Minkowski distances.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SmallMemoryKDTree.Factory<O extends NumberVector> Factory class
class	SmallMemoryKDTree.KDTreeKNNQuery kNN query for the k-d-tree.
class	SmallMemoryKDTree.KDTreeRangeQuery kNN query for the k-d-tree.

Field Summary

Fields

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) ModifiableDoubleDBIDList	sorted The actual "tree" as a sorted array.

Fields inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

relation

Constructor Summary

Constructors

Constructor and Description
SmallMemoryKDTree(Relation<O> relation, int leafsize) Constructor.

Method Summary

Methods

Modifier and Type	Method and 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.
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

Class logger

sorted

ModifiableDoubleDBIDList sorted

The actual "tree" as a sorted array.

dims

int dims

The number of dimensions.

leafsize

int leafsize

Maximum size of leaf nodes.

objaccess

final Counter objaccess

Counter for comparisons.

distcalc

final Counter distcalc

Counter for distance computations.

Constructor Detail

SmallMemoryKDTree

public SmallMemoryKDTree(Relation<O> relation,
                 int leafsize)

Constructor.

Parameters:

relation - Relation to index

leafsize - 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 interface Index

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 minimum

right - Interval maximum

axis - Current splitting axis

iter - Iterator

getLongName

public String getLongName()

Description copied from interface: Result

A "pretty" name for the result, for use in titles, captions and menus.

Specified by:

getLongName in interface Result

Specified by:

getLongName in class AbstractIndex<O extends NumberVector>

Returns:

result name

getShortName

public String getShortName()

Description copied from interface: Result

A short name for the result, useful for file names.

Specified by:

getShortName in interface Result

Specified by:

getShortName in class AbstractIndex<O extends NumberVector>

Returns:

result name

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 interface Index

countObjectAccess

protected void countObjectAccess()

Count a single object access.

countDistanceComputation

protected void countDistanceComputation()

Count a distance computation.

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery,
                      Object... hints)

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:

getKNNQuery in interface KNNIndex<O extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getRangeQuery

public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery,
                          Object... hints)

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:

getRangeQuery in interface RangeIndex<O extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null