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

Class MaterializeKNNAndRKNNPreprocessor<O>

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

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

Type Parameters:

O - the type of database objects the preprocessor can be applied to

All Implemented Interfaces:

DynamicIndex, Index, KNNIndex<O>, RKNNIndex<O>, Result

@Title(value="Materialize kNN and RkNN Neighborhood preprocessor")
@Description(value="Materializes the k nearest neighbors and the reverse k nearest neighbors of objects of a database.")
public class MaterializeKNNAndRKNNPreprocessor<O>
extends MaterializeKNNPreprocessor<O>
implements RKNNIndex<O>

A preprocessor for annotation of the k nearest neighbors and the reverse k nearest neighbors (and their distances) to each database object. BUG: This class currently does not seem able to correctly keep track of the nearest neighbors!

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	MaterializeKNNAndRKNNPreprocessor.Factory<O> The parameterizable factory.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Logger to use.
private WritableDataStore<TreeSet<DoubleDBIDPair>>	materialized_RkNN Additional data storage for RkNN.

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

knnQuery, listenerList

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
MaterializeKNNAndRKNNPreprocessor(Relation<O> relation, DistanceFunction<? super O> distanceFunction, int k) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected ArrayDBIDs	affectedkNN(List<? extends KNNList> extract, DBIDs remove) Extracts and removes the DBIDs in the given collections.
protected ArrayDBIDs	affectedRkNN(List<? extends Collection<DoubleDBIDPair>> extract, DBIDs remove) Extracts and removes the DBIDs in the given collections.
KNNList	getKNN(DBID id) Returns the materialized kNNs of the specified id.
protected Logging	getLogger() Get the classes static logger.
String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
DoubleDBIDList	getRKNN(DBIDRef id) Returns the materialized RkNNs of the specified id.
RKNNQuery<O>	getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) Get a KNN query object for the given distance query and k.
String	getShortName() A short name for the result, useful for file names.
private DoubleDBIDPair	makePair(DoubleDBIDListIter iter, DBIDIter id)
private void	materializeKNNAndRKNNs(ArrayDBIDs ids, FiniteProgress progress) Materializes the kNNs and RkNNs of the specified object IDs.
protected void	objectsInserted(DBIDs ids) Called after new objects have been inserted, updates the materialized neighborhood.
protected void	objectsRemoved(DBIDs ids) Called after objects have been removed, updates the materialized neighborhood.
protected void	preprocess() The actual preprocessing step.
private ArrayDBIDs	updateKNNsAndRkNNs(DBIDs ids) Updates the kNNs and RkNNs after insertion of the specified ids.

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

addKNNListener, delete, deleteAll, fireKNNsInserted, fireKNNsRemoved, insert, insertAll, logStatistics, removeKNNListener

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

createStorage, get, getDistanceQuery, getK, getKNNQuery, initialize

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.index.Index

initialize, logStatistics

Field Detail

LOG

private static final Logging LOG

Logger to use.

materialized_RkNN

private WritableDataStore<TreeSet<DoubleDBIDPair>> materialized_RkNN

Additional data storage for RkNN.

Constructor Detail

MaterializeKNNAndRKNNPreprocessor

public MaterializeKNNAndRKNNPreprocessor(Relation<O> relation,
                                 DistanceFunction<? super O> distanceFunction,
                                 int k)

Constructor.

Parameters:

relation - Relation to process

distanceFunction - the distance function to use

k - query k

Method Detail

preprocess

protected void preprocess()

Description copied from class: MaterializeKNNPreprocessor

The actual preprocessing step.

Overrides:

preprocess in class MaterializeKNNPreprocessor<O>

materializeKNNAndRKNNs

private void materializeKNNAndRKNNs(ArrayDBIDs ids,
                          FiniteProgress progress)

Materializes the kNNs and RkNNs of the specified object IDs.

Parameters:

ids - the IDs of the objects

makePair

private DoubleDBIDPair makePair(DoubleDBIDListIter iter,
                      DBIDIter id)

objectsInserted

protected void objectsInserted(DBIDs ids)

Description copied from class: MaterializeKNNPreprocessor

Called after new objects have been inserted, updates the materialized neighborhood.

Overrides:

objectsInserted in class MaterializeKNNPreprocessor<O>

Parameters:

ids - the ids of the newly inserted objects

updateKNNsAndRkNNs

private ArrayDBIDs updateKNNsAndRkNNs(DBIDs ids)

Updates the kNNs and RkNNs after insertion of the specified ids.

Parameters:

ids - the ids of newly inserted objects causing a change of materialized kNNs and RkNNs

Returns:

the RkNNs of the specified ids, i.e. the kNNs which have been updated

objectsRemoved

protected void objectsRemoved(DBIDs ids)

Description copied from class: MaterializeKNNPreprocessor

Called after objects have been removed, updates the materialized neighborhood.

Overrides:

objectsRemoved in class MaterializeKNNPreprocessor<O>

Parameters:

ids - the ids of the removed objects

affectedkNN

protected ArrayDBIDs affectedkNN(List<? extends KNNList> extract,
                     DBIDs remove)

Extracts and removes the DBIDs in the given collections.

Parameters:

extract - a list of lists of DistanceResultPair to extract

remove - the ids to remove

Returns:

the DBIDs in the given collection

affectedRkNN

protected ArrayDBIDs affectedRkNN(List<? extends Collection<DoubleDBIDPair>> extract,
                      DBIDs remove)

Extracts and removes the DBIDs in the given collections.

Parameters:

extract - a list of lists of DistanceResultPair to extract

remove - the ids to remove

Returns:

the DBIDs in the given collection

getKNN

public KNNList getKNN(DBID id)

Returns the materialized kNNs of the specified id.

Parameters:

id - the query id

Returns:

the kNNs

getRKNN

public DoubleDBIDList getRKNN(DBIDRef id)

Returns the materialized RkNNs of the specified id.

Parameters:

id - the query id

Returns:

the RkNNs

getRKNNQuery

public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery,
                        Object... hints)

Description copied from interface: RKNNIndex

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:

getRKNNQuery in interface RKNNIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

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

Overrides:

getLongName in class MaterializeKNNPreprocessor<O>

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

Overrides:

getShortName in class MaterializeKNNPreprocessor<O>

Returns:

result name

getLogger

protected Logging getLogger()

Description copied from class: AbstractPreprocessorIndex

Get the classes static logger.

Overrides:

getLogger in class MaterializeKNNPreprocessor<O>

Returns:

Logger