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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.index.AbstractIndex<O>
      extended by de.lmu.ifi.dbs.elki.index.preprocessed.AbstractPreprocessorIndex<O,List<DistanceResultPair<D>>>
          extended by de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor<O,D>
              extended by 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
static class MaterializeKNNPreprocessor.Factory<O,D extends Distance<D>>
          The parameterizable factory.
 
Field Summary
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
  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
 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

Release 0.4.0 (2011-09-20_1324)