Package elki.index.preprocessed.knn

Class SpacefillingKNNPreprocessor<O extends NumberVector>

java.lang.Object

elki.index.preprocessed.knn.SpacefillingKNNPreprocessor<O>

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 SpacefillingKNNPreprocessor<O extends NumberVector>
extends java.lang.Object
implements KNNIndex<O>

Compute the nearest neighbors approximatively using space filling curves.

This version computes the data projections and stores, then queries this data on-demand. This usually needs less memory (except for very small neighborhood sizes k) than SpacefillingMaterializeKNNPreprocessor, but will also be slower.

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	SpacefillingKNNPreprocessor.Factory<V extends NumberVector>	Index factory class
protected class	SpacefillingKNNPreprocessor.SpaceFillingKNNQuery	KNN Query processor for space filling curves

Field Summary

Fields

Modifier and Type	Field	Description
(package private) java.util.List<? extends SpatialSorter>	curvegen	Spatial curve generators
(package private) java.util.List<java.util.List<SpatialPair<DBID,NumberVector>>>	curves	Curve storage
private static Logging	LOG	Class logger
(package private) Mean	mean	Mean number of distance computations
(package private) int	odim	Number of dimensions to use.
(package private) WritableDataStore<int[]>	positions	Curve position storage
(package private) RandomProjectionFamily	proj	Random projection family to use.
(package private) java.util.Random	random	Random number generator.
protected Relation<O>	relation	The representation we are bound to.
(package private) int	variants	Number of variants to generate for each curve
(package private) double	window	Curve window size

Constructor Summary

Constructors

Constructor	Description
SpacefillingKNNPreprocessor(Relation<O> relation, java.util.List<? extends SpatialSorter> curvegen, double window, int variants, int odim, RandomProjectionFamily proj, java.util.Random random)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	initialize()	Initialize the index.
KNNSearcher<DBIDRef>	kNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
KNNSearcher<O>	kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
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

LOG

private static final Logging LOG

Class logger

relation

protected final Relation<O extends NumberVector> relation

The representation we are bound to.

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

curves

java.util.List<java.util.List<SpatialPair<DBID,NumberVector>>> curves

Curve storage

positions

WritableDataStore<int[]> positions

Curve position storage

mean

Mean mean

Mean number of distance computations

odim

final int odim

Number of dimensions to use.

proj

RandomProjectionFamily proj

Random projection family to use.

random

java.util.Random random

Random number generator.

Constructor Detail

SpacefillingKNNPreprocessor

public SpacefillingKNNPreprocessor(Relation<O> relation,
                                   java.util.List<? extends SpatialSorter> curvegen,
                                   double window,
                                   int variants,
                                   int odim,
                                   RandomProjectionFamily proj,
                                   java.util.Random random)

Constructor.

Parameters:

relation - Relation to index.

curvegen - Curve generators

window - Window multiplicator

variants - Number of curve variants to generate

odim - Number of dimensions to use -1 == all.

proj - Random projection to apply

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 output array.

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