Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.database
Class MetricalIndexDatabase<O extends DatabaseObject,D extends Distance<D>,N extends MetricalNode<N,E>,E extends MTreeEntry<D>>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.database.AbstractDatabase<O>
              extended by de.lmu.ifi.dbs.elki.database.IndexDatabase<O>
                  extended by de.lmu.ifi.dbs.elki.database.MetricalIndexDatabase<O,D,N,E>
Type Parameters:
O - the type of FeatureVector as element of the database
D - Distance type
N - Node type
E - Entry type
All Implemented Interfaces:
Database<O>, Result, Parameterizable, Iterable<Integer>

public class MetricalIndexDatabase<O extends DatabaseObject,D extends Distance<D>,N extends MetricalNode<N,E>,E extends MTreeEntry<D>>
extends IndexDatabase<O>

MetricalIndexDatabase is a database implementation which is supported by a metrical index structure.

Author:
Elke Achtert

Field Summary
(package private)  MetricalIndex<O,D,N,E> index
          The metrical index storing the data.
static OptionID INDEX_ID
          OptionID for INDEX_PARAM
private  ClassParameter<MetricalIndex<O,D,N,E>> INDEX_PARAM
          Parameter to specify the metrical index to use.
 
Fields inherited from class de.lmu.ifi.dbs.elki.database.AbstractDatabase
listenerList
 
Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
optionHandler
 
Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debug, logger
 
Constructor Summary
MetricalIndexDatabase()
          Constructor
 
Method Summary
<T extends Distance<T>>
List<List<DistanceResultPair<T>>>
bulkKNNQueryForID(List<Integer> ids, int k, DistanceFunction<O,T> distanceFunction)
          Performs k-nearest neighbor queries for the given object IDs.
 MetricalIndex<O,D,N,E> getIndex()
          Returns the index of this database.
 void insert(List<Pair<O,Associations>> objectsAndAssociationsList)
          Calls the super method and afterwards inserts the specified objects into the underlying index structure.
 Integer insert(Pair<O,Associations> objectAndAssociations)
          Calls the super method and afterwards inserts the specified object into the underlying index structure.
<T extends Distance<T>>
List<DistanceResultPair<T>>
kNNQueryForID(Integer id, int k, DistanceFunction<O,T> distanceFunction)
          Performs a k-nearest neighbor query for the given object ID.
<T extends Distance<T>>
List<DistanceResultPair<T>>
kNNQueryForObject(O queryObject, int k, DistanceFunction<O,T> distanceFunction)
          Performs a k-nearest neighbor query for the given object.
<T extends Distance<T>>
List<DistanceResultPair<T>>
rangeQuery(Integer id, String epsilon, DistanceFunction<O,T> distanceFunction)
          Performs a range query for the given object ID with the given epsilon range and the according distance function.
<T extends Distance<T>>
List<DistanceResultPair<T>>
reverseKNNQuery(Integer id, int k, DistanceFunction<O,T> distanceFunction)
          Performs a reverse k-nearest neighbor query for the given object ID.
 List<String> setParameters(List<String> args)
          Sets the values for the parameter bulk.
 String shortDescription()
          Returns a short description of the database.
 String toString()
          Returns a string representation of this database.
 
Methods inherited from class de.lmu.ifi.dbs.elki.database.IndexDatabase
delete, delete, getLogicalPageAccess, getPhysicalReadAccess, getPhysicalWriteReadAccess, resetPageAccess
 
Methods inherited from class de.lmu.ifi.dbs.elki.database.AbstractDatabase
addDatabaseListener, associate, associateGlobally, deleteAssociations, dimensionality, fireObjectInserted, fireObjectRemoved, fireObjectsChanged, fireObjectsInserted, fireObjectsRemoved, get, getAssociation, getAssociations, getGlobalAssociation, getIDs, getObjects, isSet, isSetForAllObjects, isSetGlobally, iterator, partition, partition, randomSample, removeDatabaseListener, restoreID, setAssociations, setNewID, size
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, progress, verbose, warning
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, collectOptions, getParameters
 

Field Detail

INDEX_ID

public static final OptionID INDEX_ID
OptionID for INDEX_PARAM


INDEX_PARAM

private final ClassParameter<MetricalIndex<O extends DatabaseObject,D extends Distance<D>,N extends MetricalNode<N,E>,E extends MTreeEntry<D>>> INDEX_PARAM
Parameter to specify the metrical index to use.

Key: -metricalindexdb.index


index

MetricalIndex<O extends DatabaseObject,D extends Distance<D>,N extends MetricalNode<N,E>,E extends MTreeEntry<D>> index
The metrical index storing the data.

Constructor Detail

MetricalIndexDatabase

public MetricalIndexDatabase()
Constructor

Method Detail

insert

public Integer insert(Pair<O,Associations> objectAndAssociations)
               throws UnableToComplyException
Calls the super method and afterwards inserts the specified object into the underlying index structure.

Specified by:
insert in interface Database<O extends DatabaseObject>
Overrides:
insert in class AbstractDatabase<O extends DatabaseObject>
Parameters:
objectAndAssociations - the object and its associations to be inserted
Returns:
the ID assigned to the inserted object
Throws:
UnableToComplyException - if database reached limit of storage capacity

insert

public void insert(List<Pair<O,Associations>> objectsAndAssociationsList)
            throws UnableToComplyException
Calls the super method and afterwards inserts the specified objects into the underlying index structure. If the option bulk load is enabled and the index structure is empty, a bulk load will be performed. Otherwise the objects will be inserted sequentially.

Specified by:
insert in interface Database<O extends DatabaseObject>
Overrides:
insert in class AbstractDatabase<O extends DatabaseObject>
Parameters:
objectsAndAssociationsList - the list of objects and their associations to be inserted
Throws:
UnableToComplyException - if initialization is not possible

rangeQuery

public <T extends Distance<T>> List<DistanceResultPair<T>> rangeQuery(Integer id,
                                                                      String epsilon,
                                                                      DistanceFunction<O,T> distanceFunction)
Description copied from interface: Database

Performs a range query for the given object ID with the given epsilon range and the according distance function.

The query result is sorted in ascending order w.r.t. the distance to the query object.

Type Parameters:
T - distance type
Parameters:
id - the ID of the query object
epsilon - the string representation of the query range
distanceFunction - the distance function that computes the distances between the objects
Returns:
a List of the query results

kNNQueryForObject

public <T extends Distance<T>> List<DistanceResultPair<T>> kNNQueryForObject(O queryObject,
                                                                             int k,
                                                                             DistanceFunction<O,T> distanceFunction)
Description copied from interface: Database

Performs a k-nearest neighbor query for the given object.

The query result is sorted in ascending order w.r.t. the distance to the query object.

The general contract for the result of kNN queries in ELKI is that the resulting list contains exactly k nearest neighbors including the query object if it is an element of this database. Generally, ties will be resolved by the order of objects in the database. Any implementing method should inform about the exact policy of resolving ties.

Generally, it is assumed that the database does not contain less than k objects.

Type Parameters:
T - distance type
Parameters:
queryObject - the query object
k - the number of nearest neighbors to be returned
distanceFunction - the distance function that computes the distances between the objects
Returns:
a List of the query results

kNNQueryForID

public <T extends Distance<T>> List<DistanceResultPair<T>> kNNQueryForID(Integer id,
                                                                         int k,
                                                                         DistanceFunction<O,T> distanceFunction)
Description copied from interface: Database

Performs a k-nearest neighbor query for the given object ID.

The query result is sorted in ascending order w.r.t. the distance to the query object.

The general contract for the result of kNN queries in ELKI is that the resulting list contains exactly k nearest neighbors including the query object. Generally, ties will be resolved by the order of objects in the database. Any implementing method should inform about the exact policy of resolving ties.

Generally, it is assumed that the database does not contain less than k objects.

Type Parameters:
T - distance type
Parameters:
id - the ID of the query object
k - the number of nearest neighbors to be returned
distanceFunction - the distance function that computes the distances between the objects
Returns:
a List of the query results

bulkKNNQueryForID

public <T extends Distance<T>> List<List<DistanceResultPair<T>>> bulkKNNQueryForID(List<Integer> ids,
                                                                                   int k,
                                                                                   DistanceFunction<O,T> distanceFunction)
Description copied from interface: Database

Performs k-nearest neighbor queries for the given object IDs.

The query result is sorted in ascending order w.r.t. the distance to the query object.

The general contract for the result of kNN queries in ELKI is that the resulting lists contain exactly k nearest neighbors including the query objects. Generally, ties will be resolved by the order of objects in the database. Any implementing method should inform about the exact policy of resolving ties.

Generally, it is assumed that the database does not contain less than k objects.

Type Parameters:
T - distance type
Parameters:
ids - the IDs of the query objects
k - the number of nearest neighbors to be returned
distanceFunction - the distance function that computes the distances between the objects
Returns:
a List of List of the query results

reverseKNNQuery

public <T extends Distance<T>> List<DistanceResultPair<T>> reverseKNNQuery(Integer id,
                                                                           int k,
                                                                           DistanceFunction<O,T> distanceFunction)
Description copied from interface: Database

Performs a reverse k-nearest neighbor query for the given object ID.

The query result is sorted in ascending order w.r.t. the distance to the query object.

Generally, it is assumed that the database does not contain less than k objects.

Type Parameters:
T - distance type
Parameters:
id - the ID of the query object
k - the size of k-nearest neighborhood of any database object o to contain a database object in order to include o in the result list
distanceFunction - the distance function that computes the distances between the objects
Returns:
a List of the query results

toString

public String toString()
Returns a string representation of this database.

Overrides:
toString in class Object
Returns:
a string representation of this database.

getIndex

public MetricalIndex<O,D,N,E> getIndex()
Returns the index of this database.

Specified by:
getIndex in class IndexDatabase<O extends DatabaseObject>
Returns:
the index of this database

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException
Sets the values for the parameter bulk. If the parameters is not specified the default value is set.

Specified by:
setParameters in interface Parameterizable
Overrides:
setParameters in class AbstractParameterizable
Parameters:
args - parameters to set the attributes accordingly to
Returns:
a list containing the unused parameters
Throws:
ParameterException - in case of wrong parameter-setting

shortDescription

public String shortDescription()
Returns a short description of the database. (Such as: efficiency in space and time, index structure...)

Specified by:
shortDescription in interface Parameterizable
Overrides:
shortDescription in class AbstractParameterizable
Returns:
a description of the database

Release 0.2.1 (2009-07-13_1605)