Class MinimalisticMemoryKDTree.KDTreeRangeSearcher

  • All Implemented Interfaces:
    RangeSearcher<O>
    Enclosing class:
    MinimalisticMemoryKDTree<O extends NumberVector>

    @Reference(authors="S. Arya and D. M. Mount",
               title="Algorithms for fast vector quantization",
               booktitle="Proc. DCC \'93: Data Compression Conference",
               url="https://doi.org/10.1109/DCC.1993.253111",
               bibkey="doi:10.1109/DCC.1993.253111")
    public class MinimalisticMemoryKDTree.KDTreeRangeSearcher
    extends java.lang.Object
    implements RangeSearcher<O>
    Range query for the k-d-tree.

    Reference:

    S. Arya and D. M. Mount
    Algorithms for fast vector quantization
    Proc. DCC '93: Data Compression Conference

    Author:
    Erich Schubert
    • Constructor Detail

      • KDTreeRangeSearcher

        public KDTreeRangeSearcher​(PartialDistance<? super O> distance)
        Constructor.
        Parameters:
        distance - Distance to use
    • Method Detail

      • kdRangeSearch

        private void kdRangeSearch​(int left,
                                   int right,
                                   int axis,
                                   O query,
                                   ModifiableDoubleDBIDList res,
                                   DBIDArrayIter iter,
                                   double[] bounds,
                                   double rawdist,
                                   double radius)
        Perform a range search on the k-d-tree.
        Parameters:
        left - Subtree begin
        right - Subtree end (exclusive)
        axis - Current splitting axis
        query - Query object
        res - kNN heap
        iter - Iterator variable (reduces memory footprint!)
        rawdist - Raw distance to current rectangle (usually squared)
        radius - Query radius