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

Class MaterializeKNNPreprocessor<O,D extends Distance<D>>

java.lang.Object

de.lmu.ifi.dbs.elki.index.AbstractIndex<O>

de.lmu.ifi.dbs.elki.index.preprocessed.AbstractPreprocessorIndex<O,List<DistanceResultPair<D>>>

de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor<O,D>

de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNPreprocessor<O,D>

Type Parameters:

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

D - the type of distance the used distance function will return

All Implemented Interfaces:

Index, KNNIndex<O>, Result

Direct Known Subclasses:

MaterializeKNNAndRKNNPreprocessor

@Title(value="Materialize kNN Neighborhood preprocessor")
@Description(value="Materializes the k nearest neighbors of objects of a database.")
public class MaterializeKNNPreprocessor<O,D extends Distance<D>>
extends AbstractMaterializeKNNPreprocessor<O,D>

A preprocessor for annotation of the k nearest neighbors (and their distances) to each database object. Used for example by LOF.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	MaterializeKNNPreprocessor.Factory<O,D extends Distance<D>> The parameterizable factory.

Field Summary

Fields

Modifier and Type	Field and Description
protected KNNQuery<O,D>	knnQuery KNNQuery instance to use.
private static Logging	logger Logger to use.
private static boolean	usebulk Flag to use bulk operations.

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

distanceFunction, distanceQuery, k, listenerList

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

Modifier	Constructor and Description
	MaterializeKNNPreprocessor(Relation<O> relation, DistanceFunction<? super O,D> distanceFunction, int k) Constructor with preprocessing step.
protected	MaterializeKNNPreprocessor(Relation<O> relation, DistanceFunction<? super O,D> distanceFunction, int k, boolean preprocess) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	addKNNListener(KNNListener l) Adds a KNNListener which will be invoked when the kNNs of objects are changing.
boolean	delete(DBID id) Deletes the specified object from this index.
void	deleteAll(DBIDs ids) Deletes the specified objects from this index.
protected ArrayDBIDs	extractAndRemoveIDs(List<List<DistanceResultPair<D>>> extraxt, ArrayDBIDs remove) Extracts and removes the DBIDs in the given collections.
protected void	fireKNNsInserted(DBIDs insertions, DBIDs updates) Informs all registered KNNListener that new kNNs have been inserted and as a result some kNNs have been changed.
protected void	fireKNNsRemoved(DBIDs removals, DBIDs updates) Informs all registered KNNListener that existing kNNs have been removed and as a result some kNNs have been changed.
List<DistanceResultPair<D>>	get(DBID objid) Get the k nearest neighbors.
protected Logging	getLogger() Get the classes static logger.
String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
String	getShortName() A short name for the result, useful for file names.
void	insert(DBID id) Inserts the specified object into this index.
void	insertAll(DBIDs ids) Inserts the specified objects into this index.
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.
void	removeKNNListener(KNNListener l) Removes a KNNListener previously added with addKNNListener(de.lmu.ifi.dbs.elki.index.preprocessed.knn.KNNListener) .
private ArrayDBIDs	updateKNNsAfterDeletion(DBIDs ids) Updates the kNNs of the RkNNs of the specified ids.
private ArrayDBIDs	updateKNNsAfterInsertion(DBIDs ids) Updates the kNNs of the RkNNs of the specified ids.

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

getDistanceFactory, getDistanceQuery, getK, getKNNQuery

Methods inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

getPageFileStatistics

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

getPageFileStatistics

Field Detail

logger

private static final Logging logger

Logger to use.

usebulk

private static final boolean usebulk

Flag to use bulk operations. TODO: right now, bulk is not that good - so don't use

See Also:

Constant Field Values

knnQuery

protected final KNNQuery<O,D extends Distance<D>> knnQuery

KNNQuery instance to use.

Constructor Detail

MaterializeKNNPreprocessor

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

Constructor with preprocessing step.

Parameters:

relation - Relation to preprocess

distanceFunction - the distance function to use

k - query k

MaterializeKNNPreprocessor

protected MaterializeKNNPreprocessor(Relation<O> relation,
                          DistanceFunction<? super O,D> distanceFunction,
                          int k,
                          boolean preprocess)

Constructor.

Parameters:

relation - Relation to preprocess

distanceFunction - the distance function to use

k - query k

Method Detail

preprocess

protected void preprocess()

The actual preprocessing step.

Specified by:

preprocess in class AbstractMaterializeKNNPreprocessor<O,D extends Distance<D>>

get

public List<DistanceResultPair<D>> get(DBID objid)

Get the k nearest neighbors.

Parameters:

objid - Object ID

Returns:

Neighbors

insert

public final void insert(DBID id)

Description copied from interface: Index

Inserts the specified object into this index.

Specified by:

insert in interface Index

Overrides:

insert in class AbstractIndex<O>

Parameters:

id - the object to be inserted

insertAll

public void insertAll(DBIDs ids)

Description copied from interface: Index

Inserts the specified objects into this index. If a bulk load mode is implemented, the objects are inserted in one bulk.

Specified by:

insertAll in interface Index

Overrides:

insertAll in class AbstractIndex<O>

Parameters:

ids - the objects to be inserted

delete

public boolean delete(DBID id)

Description copied from interface: Index

Deletes the specified object from this index.

Specified by:

delete in interface Index

Overrides:

delete in class AbstractIndex<O>

Parameters:

id - Object to remove

Returns:

true if this index did contain the object, false otherwise

deleteAll

public void deleteAll(DBIDs ids)

Description copied from interface: Index

Deletes the specified objects from this index.

Specified by:

deleteAll in interface Index

Overrides:

deleteAll in class AbstractIndex<O>

Parameters:

ids - Objects to remove

objectsInserted

protected void objectsInserted(DBIDs ids)

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

Parameters:

ids - the ids of the newly inserted objects

updateKNNsAfterInsertion

private ArrayDBIDs updateKNNsAfterInsertion(DBIDs ids)

Updates the kNNs of the RkNNs of the specified ids.

Parameters:

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

Returns:

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

updateKNNsAfterDeletion

private ArrayDBIDs updateKNNsAfterDeletion(DBIDs ids)

Updates the kNNs of the RkNNs of the specified ids.

Parameters:

ids - the ids of deleted objects causing a change of materialized kNNs

Returns:

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

objectsRemoved

protected void objectsRemoved(DBIDs ids)

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

Parameters:

ids - the ids of the removed objects

fireKNNsInserted

protected void fireKNNsInserted(DBIDs insertions,
                    DBIDs updates)

Informs all registered KNNListener that new kNNs have been inserted and as a result some kNNs have been changed.

Parameters:

insertions - the ids of the newly inserted kNNs

updates - the ids of kNNs which have been changed due to the insertions

See Also:

KNNListener

fireKNNsRemoved

protected void fireKNNsRemoved(DBIDs removals,
                   DBIDs updates)

Informs all registered KNNListener that existing kNNs have been removed and as a result some kNNs have been changed.

Parameters:

removals - the ids of the removed kNNs

updates - the ids of kNNs which have been changed due to the removals

See Also:

KNNListener

extractAndRemoveIDs

protected ArrayDBIDs extractAndRemoveIDs(List<List<DistanceResultPair<D>>> extraxt,
                             ArrayDBIDs remove)

Extracts and removes the DBIDs in the given collections.

Parameters:

extraxt - a list of lists of DistanceResultPair to extract

remove - the ids to remove

Returns:

the DBIDs in the given collection

addKNNListener

public void addKNNListener(KNNListener l)

Adds a KNNListener which will be invoked when the kNNs of objects are changing.

Parameters:

l - the listener to add

See Also:

removeKNNListener(de.lmu.ifi.dbs.elki.index.preprocessed.knn.KNNListener), KNNListener

removeKNNListener

public void removeKNNListener(KNNListener l)

Removes a KNNListener previously added with addKNNListener(de.lmu.ifi.dbs.elki.index.preprocessed.knn.KNNListener) .

Parameters:

l - the listener to remove

See Also:

addKNNListener(de.lmu.ifi.dbs.elki.index.preprocessed.knn.KNNListener), KNNListener

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

Specified by:

getLongName in class AbstractIndex<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

Specified by:

getShortName in class AbstractIndex<O>

Returns:

result name

getLogger

protected Logging getLogger()

Description copied from class: AbstractPreprocessorIndex

Get the classes static logger.

Specified by:

getLogger in class AbstractPreprocessorIndex<O,List<DistanceResultPair<D extends Distance<D>>>>

Returns:

Logger