de.lmu.ifi.dbs.elki.database
Class SequentialDatabase<O extends DatabaseObject>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.database.AbstractDatabase<O>
          de.lmu.ifi.dbs.elki.database.SequentialDatabase<O>

Type Parameters:

O - the type of FeatureVector as element of the database

All Implemented Interfaces:

Database<O>, Result, Parameterizable, Iterable<Integer>

@Description(value="Database using an in-memory hashtable and doing linear scans.")
public class SequentialDatabase<O extends DatabaseObject>
extends AbstractDatabase<O>
implements Parameterizable

SequentialDatabase is a simple implementation of a Database.

It does not support any index structure and holds all objects in main memory (as a Map).

Author:

Arthur Zimek

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.database.AbstractDatabase

listenerList

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

SequentialDatabase()
Provides a database for main memory holding all objects in a hashtable.

Method Summary

<D extends Distance<D>> List<List<DistanceResultPair<D>>>	bulkKNNQueryForID(List<Integer> ids, int k, DistanceFunction<O,D> distanceFunction) Retrieves the k nearest neighbors for the query objects.
protected Collection<Pair<OptionID,Object>>	getParameters()
<D extends Distance<D>> List<DistanceResultPair<D>>	kNNQueryForID(Integer id, int k, DistanceFunction<O,D> distanceFunction) Retrieves the k nearest neighbors for the query object.
<D extends Distance<D>> List<DistanceResultPair<D>>	kNNQueryForObject(O queryObject, int k, DistanceFunction<O,D> distanceFunction) Retrieves the k nearest neighbors for the query object.
<D extends Distance<D>> List<DistanceResultPair<D>>	rangeQuery(Integer id, D 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<DistanceResultPair<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<DistanceResultPair<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.AbstractDatabase

addDatabaseListener, associate, associateGlobally, delete, delete, deleteAssociations, dimensionality, fireObjectInserted, fireObjectRemoved, fireObjectsChanged, fireObjectsInserted, fireObjectsRemoved, get, getAssociation, getAssociations, getGlobalAssociation, getIDs, getName, getObjects, insert, insert, isSet, isSetForAllObjects, isSetGlobally, iterator, partition, partition, partition, randomSample, removeDatabaseListener, restoreID, setAssociations, setNewID, size

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, toString, wait, wait, wait

Constructor Detail

SequentialDatabase

public SequentialDatabase()

Provides a database for main memory holding all objects in a hashtable.

Method Detail

kNNQueryForObject

public <D extends Distance<D>> List<DistanceResultPair<D>> kNNQueryForObject(O queryObject,
                                                                             int k,
                                                                             DistanceFunction<O,D> distanceFunction)

Retrieves the k nearest neighbors for the query object. The result contains always exactly k objects, including the query object if it is an element of the database. Ties in case of equal distances are resolved by the underlying KNNList, see KNNList.add(DistanceResultPair).

Specified by:

kNNQueryForObject in interface Database<O extends DatabaseObject>

Type Parameters:

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

See Also:

Database.kNNQueryForObject(DatabaseObject, int, DistanceFunction)

kNNQueryForID

public <D extends Distance<D>> List<DistanceResultPair<D>> kNNQueryForID(Integer id,
                                                                         int k,
                                                                         DistanceFunction<O,D> distanceFunction)

Retrieves the k nearest neighbors for the query object. The result contains always exactly k objects. Ties in case of equal distances are resolved by the underlying KNNList, see KNNList.add(DistanceResultPair).

Specified by:

kNNQueryForID in interface Database<O extends DatabaseObject>

Type Parameters:

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

See Also:

Database.kNNQueryForObject(DatabaseObject, int, DistanceFunction)

bulkKNNQueryForID

public <D extends Distance<D>> List<List<DistanceResultPair<D>>> bulkKNNQueryForID(List<Integer> ids,
                                                                                   int k,
                                                                                   DistanceFunction<O,D> distanceFunction)

Retrieves the k nearest neighbors for the query objects. The result contains always exactly k objects. Ties in case of equal distances are resolved by the underlying KNNList, see KNNList.add(DistanceResultPair).

Specified by:

bulkKNNQueryForID in interface Database<O extends DatabaseObject>

Type Parameters:

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

See Also:

Database.kNNQueryForObject(DatabaseObject, int, DistanceFunction)

rangeQuery

public <D extends Distance<D>> List<DistanceResultPair<D>> rangeQuery(Integer id,
                                                                      String epsilon,
                                                                      DistanceFunction<O,D> 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.

Specified by:

rangeQuery in interface Database<O extends DatabaseObject>

Type Parameters:

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

rangeQuery

public <D extends Distance<D>> List<DistanceResultPair<D>> rangeQuery(Integer id,
                                                                      D epsilon,
                                                                      DistanceFunction<O,D> 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.

Specified by:

rangeQuery in interface Database<O extends DatabaseObject>

Type Parameters:

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

reverseKNNQuery

public <D extends Distance<D>> List<DistanceResultPair<D>> reverseKNNQuery(Integer id,
                                                                           int k,
                                                                           DistanceFunction<O,D> 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.

Specified by:

reverseKNNQuery in interface Database<O extends DatabaseObject>

Type Parameters:

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

getParameters

protected Collection<Pair<OptionID,Object>> getParameters()

Specified by:

getParameters in class AbstractDatabase<O extends DatabaseObject>