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)",
    public class MemoryKDTree<O extends NumberVector>
    extends java.lang.Object
    implements DistancePriorityIndex<O>
    Implementation of a static in-memory K-D-tree.


    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.

    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).
        relation - Relation to index
        leafsize - Leaf size
      • MemoryKDTree

        public MemoryKDTree​(Relation<O> relation,
                            SplitStrategy split,
                            int leafsize)
        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.
        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>
        distanceQuery - Distance query
        maxk - Maximum value of k
        flags - Hints for the optimizer
        KNN Query object or null