Class AbstractCoverTree<O>

  • Type Parameters:
    O - Object type
    All Implemented Interfaces:
    Index
    Direct Known Subclasses:
    CoverTree, SimplifiedCoverTree

    public abstract class AbstractCoverTree<O>
    extends java.lang.Object
    implements Index
    Abstract base class for cover tree variants.
    Since:
    0.7.0
    Author:
    Erich Schubert
    • Field Detail

      • relation

        protected final Relation<O> relation
        The representation we are bound to.
      • expansion

        protected final double expansion
        Constant expansion rate. 2 would be the intuitive value, but the original version used 1.3, so we copy this. This means that in every level, the cover radius shrinks by 1.3.
      • invLogExpansion

        protected final double invLogExpansion
        Logarithm base.
      • scaleBottom

        protected final int scaleBottom
        Remaining points are likely identical. For 1.3 this yields: -2700
      • distance

        protected Distance<? super O> distance
        Holds the instance of the trees distance function.
      • distanceQuery

        private DistanceQuery<O> distanceQuery
        Distance query, on the data relation.
      • distComputations

        protected long distComputations
        Distance computations performed.
      • truncate

        protected int truncate
        Stop refining the tree at this size, but build a leaf.
    • Constructor Detail

      • AbstractCoverTree

        public AbstractCoverTree​(Relation<O> relation,
                                 Distance<? super O> distance,
                                 double expansion,
                                 int truncate)
        Constructor.
        Parameters:
        relation - Data relation
        distance - Distance function
        expansion - Expansion rate
        truncate - Truncate branches with less than this number of instances
    • Method Detail

      • scaleToDist

        protected final double scaleToDist​(int s)
        Convert a scaling factor to a distance.
        Parameters:
        s - Scaling factor
        Returns:
        Distance
      • distToScale

        protected final int distToScale​(double d)
        Convert a distance to an upper scaling bound.
        Parameters:
        d - Distance
        Returns:
        Scaling bound
      • maxDistance

        protected double maxDistance​(DoubleDBIDList elems)
        Find maximum in a list via scanning.
        Parameters:
        elems - Elements
        Returns:
        Maximum distance
      • distance

        protected double distance​(DBIDRef a,
                                  DBIDRef b)
        Compute a distance (and count).
        Parameters:
        a - Object reference
        b - Object reference
        Returns:
        Distance
      • distance

        protected double distance​(O a,
                                  DBIDRef b)
        Compute a distance (and count).
        Parameters:
        a - Object reference
        b - Object reference
        Returns:
        Distance
      • excludeNotCovered

        protected void excludeNotCovered​(ModifiableDoubleDBIDList candidates,
                                         double fmax,
                                         ModifiableDoubleDBIDList collect)
        Retain all elements within the current cover.
        Parameters:
        candidates - Candidates
        fmax - Maximum distance
        collect - Far neighbors
      • collectByCover

        protected void collectByCover​(DBIDRef cur,
                                      ModifiableDoubleDBIDList candidates,
                                      double fmax,
                                      ModifiableDoubleDBIDList collect)
        Collect all elements with respect to a new routing object.
        Parameters:
        cur - Routing object
        candidates - Candidate list
        fmax - Maximum distance
        collect - Output list
      • 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
      • getLogger

        protected abstract Logging getLogger()
        Get the class logger.
        Returns:
        Logger