de.lmu.ifi.dbs.elki.index.preprocessed.knn

Class SpacefillingMaterializeKNNPreprocessor<O extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.index.AbstractIndex<O>

de.lmu.ifi.dbs.elki.index.preprocessed.AbstractPreprocessorIndex<O,KNNList>

de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor<O>

de.lmu.ifi.dbs.elki.index.preprocessed.knn.SpacefillingMaterializeKNNPreprocessor<O>

All Implemented Interfaces:

Index, KNNIndex<O>, Result

@Reference(authors="E. Schubert, A. Zimek, H.-P. Kriegel",
           title="Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles",
           booktitle="Proc. 20th International Conference on Database Systems for Advanced Applications (DASFAA)",
           url="http://dx.doi.org/10.1007/978-3-319-18123-3_2")
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:

E. Schubert, A. Zimek, H.-P. Kriegel
Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles
Proc. 20th International Conference on Database Systems for Advanced Applications (DASFAA), Hanoi, Vietnam, 2015.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SpacefillingMaterializeKNNPreprocessor.Factory<V extends NumberVector> Index factory class

Field Summary

Fields

Modifier and Type	Field and Description
(package private) List<SpatialSorter>	curvegen Spatial curve generators
private static Logging	LOG Class logger
(package private) Mean	mean Mean number of distance computations
(package private) Random	random Random number generator.
(package private) int	variants Number of variants to generate for each curve
(package private) double	window Curve window size

Fields inherited from class de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor

distanceFunction, distanceQuery, k

Fields inherited from class de.lmu.ifi.dbs.elki.index.preprocessed.AbstractPreprocessorIndex

storage

Fields inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

relation

Constructor Summary

Constructors

Constructor and Description
SpacefillingMaterializeKNNPreprocessor(Relation<O> relation, DistanceFunction<? super O> distanceFunction, int k, List<SpatialSorter> curvegen, double window, int variants, Random random) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distQ, Object... hints) Get a KNN query object for the given distance query and k.
protected Logging	getLogger() Get the classes static logger.
String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
String	getShortName() A short name for the result, useful for file names.
void	logStatistics() Send statistics to the logger, if enabled.
protected void	preprocess() Perform the preprocessing step.

Methods inherited from class de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor

createStorage, get, getDistanceQuery, getK, initialize

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

Class logger

curvegen

final List<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

Random random

Random number generator.

Constructor Detail

SpacefillingMaterializeKNNPreprocessor

public SpacefillingMaterializeKNNPreprocessor(Relation<O> relation,
                                      DistanceFunction<? super O> distanceFunction,
                                      int k,
                                      List<SpatialSorter> curvegen,
                                      double window,
                                      int variants,
                                      Random random)

Constructor.

Parameters:

relation - Relation to index.

distanceFunction - Distance function

k - k

curvegen - Curve generators

window - Window multiplicator

variants - Number of curve variants to generate

random - Random number generator

Method Detail

preprocess

protected void preprocess()

Description copied from class: AbstractMaterializeKNNPreprocessor

Perform the preprocessing step.

Specified by:

preprocess in class AbstractMaterializeKNNPreprocessor<O extends NumberVector>

getLongName

public String getLongName()

Description copied from interface: Result

A "pretty" name for the result, for use in titles, captions and menus.

Specified by:

getLongName in interface Result

Specified by:

getLongName in class AbstractIndex<O extends NumberVector>

Returns:

result name

getShortName

public String getShortName()

Description copied from interface: Result

A short name for the result, useful for file names.

Specified by:

getShortName in interface Result

Specified by:

getShortName in class AbstractIndex<O extends NumberVector>

Returns:

result name

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.

getLogger

protected Logging getLogger()

Description copied from class: AbstractPreprocessorIndex

Get the classes static logger.

Specified by:

getLogger in class AbstractPreprocessorIndex<O extends NumberVector,KNNList>

Returns:

Logger

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distQ,
                      Object... hints)

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:

getKNNQuery in interface KNNIndex<O extends NumberVector>

Overrides:

getKNNQuery in class AbstractMaterializeKNNPreprocessor<O extends NumberVector>

Parameters:

distQ - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null