Class NaiveProjectedKNNPreprocessor<O extends NumberVector>

  • All Implemented Interfaces:
    Index, KNNIndex<O>

    @Reference(authors="Erich Schubert, Arthur Zimek, Hans-Peter Kriegel",
               title="Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles",
               booktitle="Proc. 20th Int. Conf. Database Systems for Advanced Applications (DASFAA 2015)",
               url="https://doi.org/10.1007/978-3-319-18123-3_2",
               bibkey="DBLP:conf/dasfaa/SchubertZK15")
    public class NaiveProjectedKNNPreprocessor<O extends NumberVector>
    extends java.lang.Object
    implements KNNIndex<O>
    Compute the approximate k nearest neighbors using 1 dimensional projections.

    This serves as a comparison method in:

    Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
    Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles
    Proc. 20th Int. Conf. Database Systems for Advanced Applications (DASFAA 2015)

    Since:
    0.7.0
    Author:
    Erich Schubert
    • Field Detail

      • relation

        protected final Relation<O extends NumberVector> relation
        The representation we are bound to.
      • LOG

        private static final Logging LOG
        Class logger.
      • window

        final double window
        Curve window size.
      • projections

        final int projections
        Number of projections to use.
      • mean

        Mean mean
        Mean number of distance computations.
      • random

        java.util.Random random
        Random number generator.
    • Constructor Detail

      • NaiveProjectedKNNPreprocessor

        public NaiveProjectedKNNPreprocessor​(Relation<O> relation,
                                             double window,
                                             int projections,
                                             RandomProjectionFamily proj,
                                             java.util.Random random)
        Constructor.
        Parameters:
        relation - Relation to index.
        window - Window multiplicator.
        projections - Number of projections to use.
        proj - Projection family to use.
        random - Random number generator.
    • 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
      • preprocess

        protected void preprocess()
      • range

        public static int[] range​(int start,
                                  int end)
        Initialize an integer value range.
        Parameters:
        start - Starting value
        end - End value (exclusive)
        Returns:
        Array of integers start..end, excluding end.
      • randomPermutation

        public static int[] randomPermutation​(int[] out,
                                              java.util.Random random)
        Perform a random permutation of the array, in-place. Knuth / Fisher-Yates style shuffle
        Parameters:
        out - Prefilled array to be modified.
        random - Random generator.
        Returns:
        Same array.
      • 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
      • 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 KNNIndex<O extends NumberVector>
        Parameters:
        distanceQuery - Distance query
        maxk - Maximum value of k
        flags - Hints for the optimizer
        Returns:
        KNN Query object or null
      • kNNByDBID

        public KNNSearcher<DBIDRef> kNNByDBID​(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:
        kNNByDBID in interface KNNIndex<O extends NumberVector>
        Parameters:
        distanceQuery - Distance query
        maxk - Maximum value of k
        flags - Hints for the optimizer
        Returns:
        KNN Query object or null