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

Class NaiveProjectedKNNPreprocessor<O extends NumberVector>

java.lang.Object

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

All Implemented Interfaces:

Index, KNNIndex<O>, Result

@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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	NaiveProjectedKNNPreprocessor.Factory<V extends NumberVector> Index factory class
protected class	NaiveProjectedKNNPreprocessor.NaiveProjectedKNNQuery KNN Query processor for naive projections.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Class logger.
(package private) Mean	mean Mean number of distance computations.
(package private) WritableDataStore<int[]>	positions Curve position storage
(package private) RandomProjectionFamily	proj Random projection family to use.
(package private) java.util.List<ModifiableDoubleDBIDList>	projected Projected data.
(package private) int	projections Number of projections to use.
(package private) java.util.Random	random Random number generator.
protected Relation<O>	relation The representation we are bound to.
(package private) double	window Curve window size.

Constructor Summary

Constructors

Constructor and Description
NaiveProjectedKNNPreprocessor(Relation<O> relation, double window, int projections, RandomProjectionFamily proj, java.util.Random random) Constructor.

Method Summary

Modifier and Type	Method and Description
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
java.lang.String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
java.lang.String	getShortName() A short name for the result, useful for file names.
void	initialize() Initialize the index.
void	logStatistics() Send statistics to the logger, if enabled.
protected void	preprocess()
static int[]	randomPermutation(int[] out, java.util.Random random) Perform a random permutation of the array, in-place.
static int[]	range(int start, int end) Initialize an integer value range.

Methods inherited from class java.lang.Object

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

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.

positions

WritableDataStore<int[]> positions

Curve position storage

mean

Mean mean

Mean number of distance computations.

proj

RandomProjectionFamily proj

Random projection family to use.

random

java.util.Random random

Random number generator.

projected

java.util.List<ModifiableDoubleDBIDList> projected

Projected data.

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.

getLongName

public java.lang.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

Returns:

result name

getShortName

public java.lang.String getShortName()

Description copied from interface: Result

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

Specified by:

getShortName in interface Result

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.

Specified by:

logStatistics in interface Index

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery,
                               java.lang.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>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null