Package elki.database.query

Class ExactPrioritySearcher<O>

  • Type Parameters:
    O - Object type
    All Implemented Interfaces:
    DBIDIter, DBIDRef, KNNSearcher<O>, PrioritySearcher<O>, RangeSearcher<O>, Iter
    public class ExactPrioritySearcher<O>
extends java.lang.Object
implements PrioritySearcher<O>
    Priority searcher that refines all objects to their exact distances, using another priority searcher inside to provide candidates. This class allows accessing the kNN in increasing order (without storing all of them, depending on the index).

    We experimented with a queue of elements where only a lower bound of the distance was available, and tried to lazily refine them, but there would only be one element in this queue by the allLowerBound requirement on the inner query.

    Since:
    0.8.0
    Author:
    Erich Schubert

    • Field Detail

      • threshold

        private double threshold
        Distance threshold

    • Constructor Detail

      • ExactPrioritySearcher

        public ExactPrioritySearcher​(PrioritySearcher<O> inner)
        Constructor.
        Parameters:
        inner - Inner query

    • Method Detail

      • decreaseCutoff

        public PrioritySearcher<O> decreaseCutoff​(double threshold)
        Description copied from interface: PrioritySearcher
        Decrease the cutoff threshold.

        The cutoff must not be increased, as the search may have pruned some results automatically.

        Specified by:
        decreaseCutoff in interface PrioritySearcher<O>
        Parameters:
        threshold - Threshold parameter
        Returns:
        this, for chaining

      • getApproximateDistance

        public double getApproximateDistance()
        Description copied from interface: PrioritySearcher
        Get approximate distance (if available).

        Quality guarantees may vary a lot!

        Specified by:
        getApproximateDistance in interface PrioritySearcher<O>
        Returns:
        Double.NaN if not valid

      • getApproximateAccuracy

        public double getApproximateAccuracy()
        Description copied from interface: PrioritySearcher
        Get approximate distance accuracy (if available).

        Quality guarantees may vary a lot!

        Specified by:
        getApproximateAccuracy in interface PrioritySearcher<O>
        Returns:
        Double.NaN if not valid

      • getLowerBound

        public double getLowerBound()
        Description copied from interface: PrioritySearcher
        Get the lower bound (if available).

        Note: the lower bound is already checked by the cutoff of the priority search, so this is primarily useful for analyzing the search behavior.

        Specified by:
        getLowerBound in interface PrioritySearcher<O>
        Returns:
        Double.NaN if not valid

      • getUpperBound

        public double getUpperBound()
        Description copied from interface: PrioritySearcher
        Get the upper bound (if available).
        Specified by:
        getUpperBound in interface PrioritySearcher<O>
        Returns:
        Double.NaN if not valid

      • computeExactDistance

        public double computeExactDistance()
        Description copied from interface: PrioritySearcher
        Compute the exact distance to the current candidate.

        The searcher may or may not have this value already.

        Specified by:
        computeExactDistance in interface PrioritySearcher<O>
        Returns:
        Distance

      • internalGetIndex

        public int internalGetIndex()
        Description copied from interface: DBIDRef
        Internal only: Get the internal index.

        NOT FOR PUBLIC USE - ELKI Optimization engine only.

        Specified by:
        internalGetIndex in interface DBIDRef
        Returns:
        Internal index

      • allLowerBound

        public double allLowerBound()
        Description copied from interface: PrioritySearcher
        Lower bound for all subsequent instances (that have been completely explored). The searcher guarantees that no further results will be returned with a distance less than this.
        Specified by:
        allLowerBound in interface PrioritySearcher<O>
        Returns:
        lower bound; 0 if no guarantees (e.g., linear scan)

      • valid

        public boolean valid()
        Description copied from interface: Iter
        Returns true if the iterator currently points to a valid object.
        Specified by:
        valid in interface Iter
        Returns:
        a boolean value, whether the position is valid.