Class SmallMemoryKDTree.KDTreeKNNSearcher

  • All Implemented Interfaces:
    KNNSearcher<O>
    Enclosing class:
    SmallMemoryKDTree<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 SmallMemoryKDTree.KDTreeKNNSearcher
    extends java.lang.Object
    implements KNNSearcher<O>
    kNN 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
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      KNNList getKNN​(O obj, int k)
      Get the k nearest neighbors for a particular object.
      private double kdKNNSearch​(int left, int right, int axis, O query, KNNHeap knns, DoubleDBIDListIter iter, double[] bounds, double rawdist, double maxdist)
      Perform a kNN search on the k-d-tree.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • KDTreeKNNSearcher

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

      • getKNN

        public KNNList getKNN​(O obj,
                              int k)
        Description copied from interface: KNNSearcher
        Get the k nearest neighbors for a particular object.
        Specified by:
        getKNN in interface KNNSearcher<O extends NumberVector>
        Parameters:
        obj - query object
        k - Number of neighbors requested
        Returns:
        neighbors
      • kdKNNSearch

        private double kdKNNSearch​(int left,
                                   int right,
                                   int axis,
                                   O query,
                                   KNNHeap knns,
                                   DoubleDBIDListIter iter,
                                   double[] bounds,
                                   double rawdist,
                                   double maxdist)
        Perform a kNN search on the k-d-tree.
        Parameters:
        left - Subtree begin
        right - Subtree end (exclusive)
        axis - Current splitting axis
        query - Query object
        knns - kNN heap
        iter - Iterator variable (reduces memory footprint!)
        bounds - current bounds
        rawdist - Raw distance to current rectangle (usually squared)
        maxdist - Current upper bound of kNN distance.
        Returns:
        New upper bound of kNN distance.