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

Class NNDescent<O>

java.lang.Object

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.NNDescent<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, KNNIndex<O>, Result

@Reference(authors="W. Dong, C. Moses, K. Li",
           title="Efficient k-nearest neighbor graph construction for generic similarity measures",
           booktitle="Proc. 20th Int. Conf. on World Wide Web (WWW\'11)",
           url="https://doi.org/10.1145/1963405.1963487",
           bibkey="DBLP:conf/www/DongCL11")
public class NNDescent<O>
extends AbstractMaterializeKNNPreprocessor<O>

NN-desent (also known as KNNGraph) is an approximate nearest neighbor search algorithm beginning with a random sample, then iteratively refining this sample until.

Reference:

W. Dong and C. Moses and K. Li
Efficient k-nearest neighbor graph construction for generic similarity measures
Proc. 20th Int. Conf. on World Wide Web (WWW'11)

Since:

0.7.5

Author:

Evelyn Kirner

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	NNDescent.Factory<O> Index factory.

Field Summary

Fields

Modifier and Type	Field and Description
private double	delta early termination parameter
private int	iterations maximum number of iterations
private static Logging	LOG Logger
private boolean	noInitialNeighbors Do not use initial neighbors
private java.lang.String	prefix Log prefix.
private double	rho sample rate
private RandomFactory	rnd Random generator
private WritableDataStore<KNNHeap>	store store for neighbors

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

relation, storage

Constructor Summary

Constructors

Constructor and Description
NNDescent(Relation<O> relation, DistanceFunction<? super O> distanceFunction, int k, RandomFactory rnd, double delta, double rho, boolean noInitialNeighbors, int iterations) Constructor.

Method Summary

Modifier and Type	Method and Description
private boolean	add(DBIDRef cur, DBIDRef cand, double distance) Add cand to cur's heap neighbors with distance
private void	addpair(WritableDataStore<HashSetModifiableDBIDs> newNeighbors, DBIDRef o1, DBIDRef o2)
private void	boundSize(HashSetModifiableDBIDs set, int items) Bound the size of a set by random sampling.
private void	clearAll(DBIDs ids, WritableDataStore<HashSetModifiableDBIDs> sets) Clear (but reuse) all sets in the given storage.
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
protected Logging	getLogger() Get the classes static logger.
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	logStatistics() Send statistics to the logger, if enabled.
protected void	preprocess() Perform the preprocessing step.
private int	processNewNeighbors(WritableDataStore<HashSetModifiableDBIDs> flag, HashSetModifiableDBIDs newFwd, HashSetModifiableDBIDs oldFwd, HashSetModifiableDBIDs newRev, HashSetModifiableDBIDs oldRev) Process new neighbors.
private void	reverse(WritableDataStore<HashSetModifiableDBIDs> sampleNewHash, WritableDataStore<HashSetModifiableDBIDs> newReverseNeighbors, WritableDataStore<HashSetModifiableDBIDs> oldReverseNeighbors) calculates new and old neighbors for database
private int	sampleNew(DBIDs ids, WritableDataStore<HashSetModifiableDBIDs> sampleNewNeighbors, WritableDataStore<HashSetModifiableDBIDs> newNeighborHash, int items) samples newNeighbors for every object

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

Logger

prefix

private java.lang.String prefix

Log prefix.

rnd

private final RandomFactory rnd

Random generator

delta

private double delta

early termination parameter

rho

private double rho

sample rate

iterations

private int iterations

maximum number of iterations

noInitialNeighbors

private boolean noInitialNeighbors

Do not use initial neighbors

store

private WritableDataStore<KNNHeap> store

store for neighbors

Constructor Detail

NNDescent

public NNDescent(Relation<O> relation,
                 DistanceFunction<? super O> distanceFunction,
                 int k,
                 RandomFactory rnd,
                 double delta,
                 double rho,
                 boolean noInitialNeighbors,
                 int iterations)

Constructor.

Parameters:

relation - Relation to index

distanceFunction - distance function

k - k

rnd - Random generator

delta - Delta threshold

rho - Rho threshold

noInitialNeighbors - Do not use initial neighbors

iterations - Maximum number of iterations

Method Detail

preprocess

protected void preprocess()

Description copied from class: AbstractMaterializeKNNPreprocessor

Perform the preprocessing step.

Specified by:

preprocess in class AbstractMaterializeKNNPreprocessor<O>

clearAll

private void clearAll(DBIDs ids,
                      WritableDataStore<HashSetModifiableDBIDs> sets)

Clear (but reuse) all sets in the given storage.

Parameters:

ids - Ids to process

sets - Sets to clear

boundSize

private void boundSize(HashSetModifiableDBIDs set,
                       int items)

Bound the size of a set by random sampling.

Parameters:

set - Set to process

items - Maximum size

processNewNeighbors

private int processNewNeighbors(WritableDataStore<HashSetModifiableDBIDs> flag,
                                HashSetModifiableDBIDs newFwd,
                                HashSetModifiableDBIDs oldFwd,
                                HashSetModifiableDBIDs newRev,
                                HashSetModifiableDBIDs oldRev)

Process new neighbors. This is a complex join, because we do not need to join old neighbors with old neighbors, and we have forward- and reverse neighbors each.

Parameters:

flag - Flags to mark new neighbors.

newFwd - New forward neighbors

oldFwd - Old forward neighbors

newRev - New reverse neighbors

oldRev - Old reverse neighbors

Returns:

Number of new neighbors

add

private boolean add(DBIDRef cur,
                    DBIDRef cand,
                    double distance)

Add cand to cur's heap neighbors with distance

Parameters:

cur - Current object

cand - Neighbor candidate

distance - Distance

Returns:

true if it was a new neighbor.

addpair

private void addpair(WritableDataStore<HashSetModifiableDBIDs> newNeighbors,
                     DBIDRef o1,
                     DBIDRef o2)

sampleNew

private int sampleNew(DBIDs ids,
                      WritableDataStore<HashSetModifiableDBIDs> sampleNewNeighbors,
                      WritableDataStore<HashSetModifiableDBIDs> newNeighborHash,
                      int items)

samples newNeighbors for every object

Parameters:

ids - All ids

sampleNewNeighbors - Output of sampled new neighbors

newNeighborHash - - new neighbors for every object

items - Number of items to collect

Returns:

Number of new neighbors

reverse

private void reverse(WritableDataStore<HashSetModifiableDBIDs> sampleNewHash,
                     WritableDataStore<HashSetModifiableDBIDs> newReverseNeighbors,
                     WritableDataStore<HashSetModifiableDBIDs> oldReverseNeighbors)

calculates new and old neighbors for database

Parameters:

sampleNewHash - new neighbors for every object

newReverseNeighbors - new reverse neighbors

oldReverseNeighbors - old reverse neighbors

getLogger

protected Logging getLogger()

Description copied from class: AbstractPreprocessorIndex

Get the classes static logger.

Specified by:

getLogger in class AbstractPreprocessorIndex<O,KNNList>

Returns:

Logger

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.

getLongName

public java.lang.String getLongName()

Description copied from interface: Result

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

Returns:

result name

getShortName

public java.lang.String getShortName()

Description copied from interface: Result

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

Returns:

result name

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>

Overrides:

getKNNQuery in class AbstractMaterializeKNNPreprocessor<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null