java.lang.Object
- elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor<O>
- - elki.index.preprocessed.knn.NNDescent<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, KNNIndex<O>
```
@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-descent (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)
TODO: collect and log some query statistics.

Since:

0.7.5

Author:

Evelyn Kirner

Nested Class Summary

Nested Classes
Modifier and Type Class Description

static class NNDescent.Factory<O>
Index factory.

Field Summary

Fields
Modifier and Type	Field	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 elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor
distance, distanceQuery, k, relation, storage

Constructor Summary

Constructors
Constructor	Description
`NNDescent(Relation<O> relation, Distance<? super O> distance, int k, RandomFactory rnd, double delta, double rho, boolean noInitialNeighbors, int iterations)`	Constructor.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	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.
`protected Logging`	`getLogger()`	Get the classes static logger.
`KNNSearcher<O>`	`kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)`	Get a KNN query object for the given distance query and k.
`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 elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor
createStorage, get, getDistanceQuery, getK, initialize, kNNByDBID

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.index.Index
logStatistics

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,
                 Distance<? super O> distance,
                 int k,
                 RandomFactory rnd,
                 double delta,
                 double rho,
                 boolean noInitialNeighbors,
                 int iterations)

Constructor.

Parameters:: relation - Relation to index; distance - 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: AbstractMaterializeKNNPreprocessor
  
  Get the classes static logger.
  
  Specified by:
  
  getLogger in class AbstractMaterializeKNNPreprocessor<O>
  
  Returns:
  
  Logger
- 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>
  
  Overrides:
  
  kNNByObject in class AbstractMaterializeKNNPreprocessor<O>
  
  Parameters:
  
  distanceQuery - Distance query
  
  maxk - Maximum value of k
  
  flags - Hints for the optimizer
  
  Returns:
  
  KNN Query object or null

Class NNDescent<O>

Nested Class Summary

Field Summary

Fields inherited from class elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor

Constructor Summary

Method Summary

Methods inherited from class elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor

Methods inherited from class java.lang.Object

Methods inherited from interface elki.index.Index

Field Detail

LOG

prefix

rnd

delta

rho

iterations

noInitialNeighbors

store

Constructor Detail

NNDescent

Method Detail

preprocess

clearAll

boundSize

processNewNeighbors

add

addpair

sampleNew

reverse

getLogger

kNNByObject