Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.database
Class InvertedListDatabase<N extends Number,O extends FeatureVector<O,N>>

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.SequentialDatabase<O>
                  extended by de.lmu.ifi.dbs.elki.database.InvertedListDatabase<N,O>
All Implemented Interfaces:
Database<O>, Loggable, Parameterizable

public class InvertedListDatabase<N extends Number,O extends FeatureVector<O,N>>
extends SequentialDatabase<O>

Database implemented by inverted lists that supports range queries on a specific dimension.

Author:
Elke Achtert

Field Summary
private  Map<Integer,SortedMap<Double,List<Integer>>> invertedLists
          Map to hold the inverted lists for each dimension.
 
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
 
Constructor Summary
InvertedListDatabase()
           
 
Method Summary
<D extends Distance<D>>
List<List<QueryResult<D>>>
bulkKNNQueryForID(List<Integer> ids, int k, DistanceFunction<O,D> distanceFunction)
          Performs k-nearest neighbor queries for the given object IDs.
 O delete(Integer id)
          Removes and returns the object with the given id from the database.
 Integer insert(ObjectAndAssociations<O> objectAndAssociations)
          Inserts the given object into the database.
<D extends Distance<D>>
List<QueryResult<D>>
kNNQueryForID(Integer id, int k, DistanceFunction<O,D> distanceFunction)
          Performs a k-nearest neighbor query for the given object ID.
<D extends Distance<D>>
List<QueryResult<D>>
kNNQueryForObject(O queryObject, int k, DistanceFunction<O,D> distanceFunction)
          Performs a k-nearest neighbor query for the given object.
<D extends Distance<D>>
List<QueryResult<D>>
rangeQuery(Integer id, String epsilon, DistanceFunction<O,D> distanceFunction)
          Performs a range query for the given object ID with the given epsilon range and the according distance function.
<D extends Distance<D>>
List<QueryResult<D>>
reverseKNNQuery(Integer id, int k, DistanceFunction<O,D> distanceFunction)
          Performs a reverse k-nearest neighbor query for the given object ID.
 
Methods inherited from class de.lmu.ifi.dbs.elki.database.SequentialDatabase
description
 
Methods inherited from class de.lmu.ifi.dbs.elki.database.AbstractDatabase
addDatabaseListener, associate, associateGlobally, delete, deleteAssociations, dimensionality, fireObjectInserted, fireObjectRemoved, fireObjectsChanged, fireObjectsInserted, fireObjectsRemoved, get, getAssociation, getAssociations, getGlobalAssociation, getIDs, getObjects, insert, 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, checkGlobalParameterConstraints, deleteOption, description, description, getAttributeSettings, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters, setParameters
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning
 
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.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription, setParameters
 

Field Detail

invertedLists

private Map<Integer,SortedMap<Double,List<Integer>>> invertedLists
Map to hold the inverted lists for each dimension.

Constructor Detail

InvertedListDatabase

public InvertedListDatabase()
Method Detail

insert

public Integer insert(ObjectAndAssociations<O> objectAndAssociations)
               throws UnableToComplyException
Description copied from interface: Database
Inserts the given object into the database.

Specified by:
insert in interface Database<O extends FeatureVector<O,N>>
Overrides:
insert in class AbstractDatabase<O extends FeatureVector<O,N>>
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
See Also:
Database.insert(de.lmu.ifi.dbs.elki.database.ObjectAndAssociations)

delete

public O delete(Integer id)
Description copied from interface: Database
Removes and returns the object with the given id from the database.

Specified by:
delete in interface Database<O extends FeatureVector<O,N>>
Overrides:
delete in class AbstractDatabase<O extends FeatureVector<O,N>>
Parameters:
id - the id of an object to be removed from the database
Returns:
the object that has been removed
See Also:
Database.delete(Integer)

rangeQuery

public <D extends Distance<D>> List<QueryResult<D>> rangeQuery(Integer id,
                                                               String epsilon,
                                                               DistanceFunction<O,D> distanceFunction)
Performs a range query for the given object ID with the given epsilon range and the according distance function. The query result is in ascending order to the distance to the query object.

Specified by:
rangeQuery in interface Database<O extends FeatureVector<O,N>>
Overrides:
rangeQuery in class SequentialDatabase<O extends FeatureVector<O,N>>
Parameters:
id - the ID of the query object
epsilon - the string representation of the query range
distanceFunction - the distance function that computes the distances beween the objects
Returns:
a List of the query results
See Also:
Database.rangeQuery(java.lang.Integer, java.lang.String, de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction)

kNNQueryForID

public <D extends Distance<D>> List<QueryResult<D>> kNNQueryForID(Integer id,
                                                                  int k,
                                                                  DistanceFunction<O,D> distanceFunction)
Performs a k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.

Specified by:
kNNQueryForID in interface Database<O extends FeatureVector<O,N>>
Overrides:
kNNQueryForID in class SequentialDatabase<O extends FeatureVector<O,N>>
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 beween the objects
Returns:
a List of the query results
See Also:
Database.kNNQueryForID(java.lang.Integer, int, de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction)

kNNQueryForObject

public <D extends Distance<D>> List<QueryResult<D>> kNNQueryForObject(O queryObject,
                                                                      int k,
                                                                      DistanceFunction<O,D> distanceFunction)
Performs a k-nearest neighbor query for the given object. The query result is in ascending order to the distance to the query object.

Specified by:
kNNQueryForObject in interface Database<O extends FeatureVector<O,N>>
Overrides:
kNNQueryForObject in class SequentialDatabase<O extends FeatureVector<O,N>>
Parameters:
queryObject - the query object
k - the number of nearest neighbors to be returned
distanceFunction - the distance function that computes the distances beween the objects
Returns:
a List of the query results
See Also:
Database.kNNQueryForObject(DatabaseObject, int, de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction)

bulkKNNQueryForID

public <D extends Distance<D>> List<List<QueryResult<D>>> bulkKNNQueryForID(List<Integer> ids,
                                                                            int k,
                                                                            DistanceFunction<O,D> distanceFunction)
Performs k-nearest neighbor queries for the given object IDs. The query result is in ascending order to the distance to the query object.

Specified by:
bulkKNNQueryForID in interface Database<O extends FeatureVector<O,N>>
Overrides:
bulkKNNQueryForID in class SequentialDatabase<O extends FeatureVector<O,N>>
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 beween the objects
Returns:
a List of List of the query results
See Also:
Database.bulkKNNQueryForID(java.util.List, int, de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction)

reverseKNNQuery

public <D extends Distance<D>> List<QueryResult<D>> reverseKNNQuery(Integer id,
                                                                    int k,
                                                                    DistanceFunction<O,D> distanceFunction)
Performs a reverse k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.

Specified by:
reverseKNNQuery in interface Database<O extends FeatureVector<O,N>>
Overrides:
reverseKNNQuery in class SequentialDatabase<O extends FeatureVector<O,N>>
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 beween the objects
Returns:
a List of the query results
See Also:
Database.reverseKNNQuery(Integer, int, de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction)

Release 0.1 (2008-07-10_1838)