Package elki.index.tree.spatial.kd

Class MemoryKDTree<O extends NumberVector>

  • 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 Conference

    TODO: add support for weighted Minkowski distances.

    Since:
    0.7.0
    Author:
    Erich Schubert

    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger

      • relation

        protected final Relation<O extends NumberVector> relation
        The representation we are bound to.

      • 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 index
        leafsize - Leaf size

      • MemoryKDTree

        public MemoryKDTree​(Relation<O> relation,
                    SplitStrategy split,
                    int leafsize)
        Constructor.
        Parameters:
        relation - Relation to index
        split - Split strategy
        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

      • 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 start
        pos - Split position
        right - Interval end
        dim - Split dimension
        val - Split threshold
        iter - 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 interface Index

      • 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 interface DistancePriorityIndex<O extends NumberVector>
        Specified by:
        kNNByObject in interface KNNIndex<O extends NumberVector>
        Parameters:
        distanceQuery - Distance query
        maxk - Maximum value of k
        flags - Hints for the optimizer
        Returns:
        KNN Query object or null