Class SpacefillingMaterializeKNNPreprocessor<O extends NumberVector>

  • Type Parameters:
    O - Vector type indexed
    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 SpacefillingMaterializeKNNPreprocessor<O extends NumberVector>
    extends AbstractMaterializeKNNPreprocessor<O>
    Compute the nearest neighbors approximatively using space filling curves.

    This version does the bulk kNN-join operation, i.e. precomputes the k nearest neighbors for every object, then discards the curves. This is usually more memory intensive but faster than SpacefillingKNNPreprocessor.

    Reference:

    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

      • LOG

        private static final Logging LOG
        Class logger
      • curvegen

        final java.util.List<? extends SpatialSorter> curvegen
        Spatial curve generators
      • window

        final double window
        Curve window size
      • variants

        final int variants
        Number of variants to generate for each curve
      • mean

        Mean mean
        Mean number of distance computations
      • random

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

      • SpacefillingMaterializeKNNPreprocessor

        public SpacefillingMaterializeKNNPreprocessor​(Relation<O> relation,
                                                      Distance<? super O> distance,
                                                      int k,
                                                      java.util.List<? extends SpatialSorter> curvegen,
                                                      double window,
                                                      int variants,
                                                      java.util.Random random)
        Constructor.
        Parameters:
        relation - Relation to index.
        distance - Distance function
        k - k
        curvegen - Curve generators
        window - Window multiplicator
        variants - Number of curve variants to generate
        random - Random number generator