Package elki.index.preprocessed.knn

Class MaterializeKNNAndRKNNPreprocessor<O>

java.lang.Object

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

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

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

Type Parameters:

O - the type of database objects the preprocessor can be applied to the type of distance the used distance function will return

All Implemented Interfaces:

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

@Title("Materialize kNN and RkNN Neighborhood preprocessor")
@Description("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?

TODO: for better performance, we would need some ModifiableDoubleDBIDHashSet or TreeSet to store the rkNN.

Since:

0.4.0

Author:

Elke Achtert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

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

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

knnQuery, listenerList

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

distance, distanceQuery, k, relation, storage

Constructor Summary

Constructors

Constructor	Description
MaterializeKNNAndRKNNPreprocessor(Relation<O> relation, Distance<? super O> distance, int k)	Constructor.

Method Summary

Modifier and Type	Method	Description
KNNList	getKNN(DBID id)	Returns the materialized kNNs of the specified id.
protected Logging	getLogger()	Get the classes static logger.
DoubleDBIDList	getRKNN(DBIDRef id)	Returns the materialized RkNNs of the specified 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.
RKNNSearcher<DBIDRef>	rkNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a RKNN query object for the given distance query and k.
RKNNSearcher<O>	rkNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a RKNN query object for the given distance query and k.
private DBIDs	updateKNNsAndRkNNs(DBIDs ids)	Updates the kNNs and RkNNs after insertion of the specified ids.

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

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

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

createStorage, get, getDistanceQuery, getK, initialize, kNNByDBID, kNNByObject

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

initialize, logStatistics

Field Detail

LOG

private static final Logging LOG

Logger to use.

storageRkNN

private WritableDataStore<ModifiableDoubleDBIDList> storageRkNN

Additional data storage for RkNN.

Constructor Detail

MaterializeKNNAndRKNNPreprocessor

public MaterializeKNNAndRKNNPreprocessor(Relation<O> relation,
                                         Distance<? super O> distance,
                                         int k)

Constructor.

Parameters:

relation - Relation to process

distance - 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

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 DBIDs 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

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

rkNNByObject

public RKNNSearcher<O> rkNNByObject(DistanceQuery<O> distanceQuery,
                                    int maxk,
                                    int flags)

Description copied from interface: RKNNIndex

Get a RKNN query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

rkNNByObject in interface RKNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum k for RkNN query

flags - Hints for the optimizer

Returns:

RKNN Query object or null

rkNNByDBID

public RKNNSearcher<DBIDRef> rkNNByDBID(DistanceQuery<O> distanceQuery,
                                        int maxk,
                                        int flags)

Description copied from interface: RKNNIndex

Get a RKNN query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

rkNNByDBID in interface RKNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum k for RkNN query

flags - Hints for the optimizer

Returns:

RKNN Query object or null

getLogger

protected Logging getLogger()

Description copied from class: AbstractMaterializeKNNPreprocessor

Get the classes static logger.

Overrides:

getLogger in class MaterializeKNNPreprocessor<O>

Returns:

Logger