de.lmu.ifi.dbs.elki.index.tree.spatial
Class SpatialIndex<O extends NumberVector<O,?>,N extends SpatialNode<N,E>,E extends SpatialEntry>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex<O,N,E>

All Implemented Interfaces:

Index<O>, Loggable, Parameterizable

Direct Known Subclasses:

AbstractRStarTree

public abstract class SpatialIndex<O extends NumberVector<O,?>,N extends SpatialNode<N,E>,E extends SpatialEntry>
extends TreeIndex<O,N,E>

Abstract super class for all spatial index classes.

Author:

Elke Achtert

Field Summary

protected boolean	bulk If true, a bulk load will be performed.
static String	BULK_LOAD_D Description for parameter bulk.
static String	BULK_LOAD_F Option string for parameter bulk.
static String	BULK_LOAD_STRATEGY_D Description for parameter bulkstrategy.
static String	BULK_LOAD_STRATEGY_P Option string for parameter bulkstrategy.
protected BulkSplit.Strategy	bulkLoadStrategy The strategy for bulk load.

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex

CACHE_SIZE_D, CACHE_SIZE_P, cacheSize, DEFAULT_CACHE_SIZE, DEFAULT_PAGE_SIZE, dirCapacity, dirMinimum, file, FILE_NAME_D, FILE_NAME_P, initialized, leafCapacity, leafMinimum, PAGE_SIZE_D, PAGE_SIZE_P, pageSize

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

SpatialIndex()

Method Summary

abstract <D extends Distance<D>> List<List<QueryResult<D>>>	bulkKNNQueryForIDs(List<Integer> ids, int k, SpatialDistanceFunction<O,D> distanceFunction) Performs a bulk k-nearest neighbor query for the given object IDs.
abstract List<E>	getLeaves() Returns a list of entries pointing to the leaf nodes of this spatial index.
abstract <D extends Distance<D>> List<QueryResult<D>>	kNNQuery(O obj, int k, DistanceFunction<O,D> distanceFunction) Performs a k-nearest neighbor query for the given object with the given parameter k and the according distance function.
abstract <D extends Distance<D>> List<QueryResult<D>>	rangeQuery(O obj, String epsilon, DistanceFunction<O,D> distanceFunction) Performs a range query for the given object with the given epsilon range and the according distance function.
abstract <D extends Distance<D>> List<QueryResult<D>>	reverseKNNQuery(O object, int k, DistanceFunction<O,D> distanceFunction) Performs a reverse k-nearest neighbor query for the given object ID.
void	setDatabase(Database<O> database) Sets the databse in the distance function of this index (if existing).
String[]	setParameters(String[] args) Sets the attributes of the class accordingly to the given parameters.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex

close, createEmptyRoot, createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, description, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeCapacities, initializeFromFile, postDelete, preInsert, resetPageAccess

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getAttributeSettings, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, 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.index.Index

delete, insert, insert

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription

Field Detail

BULK_LOAD_F

public static final String BULK_LOAD_F

Option string for parameter bulk.

See Also:

Constant Field Values

BULK_LOAD_D

public static final String BULK_LOAD_D

Description for parameter bulk.

See Also:

Constant Field Values

BULK_LOAD_STRATEGY_P

public static final String BULK_LOAD_STRATEGY_P

Option string for parameter bulkstrategy.

See Also:

Constant Field Values

BULK_LOAD_STRATEGY_D

public static final String BULK_LOAD_STRATEGY_D

Description for parameter bulkstrategy.

bulk

protected boolean bulk

If true, a bulk load will be performed.

bulkLoadStrategy

protected BulkSplit.Strategy bulkLoadStrategy

The strategy for bulk load.

Constructor Detail

SpatialIndex

public SpatialIndex()

Method Detail

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Description copied from interface: Parameterizable

Sets the attributes of the class accordingly to the given parameters. Returns a new String array containing those entries of the given array that are neither expected nor used by this Parameterizable.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class TreeIndex<O extends NumberVector<O,?>,N extends SpatialNode<N,E>,E extends SpatialEntry>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

setDatabase

public void setDatabase(Database<O> database)

Sets the databse in the distance function of this index (if existing). Subclasses may need to overwrite this method.

Parameters:

database - the database

rangeQuery

public abstract <D extends Distance<D>> List<QueryResult<D>> rangeQuery(O obj,
                                                                        String epsilon,
                                                                        DistanceFunction<O,D> distanceFunction)

Performs a range query for the given object with the given epsilon range and the according distance function. The query result is in ascending order to the distance to the query object.

Parameters:

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

kNNQuery

public abstract <D extends Distance<D>> List<QueryResult<D>> kNNQuery(O obj,
                                                                      int k,
                                                                      DistanceFunction<O,D> distanceFunction)

Performs a k-nearest neighbor query for the given object with the given parameter k and the according distance function. The query result is in ascending order to the distance to the query object.

Parameters:

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

reverseKNNQuery

public abstract <D extends Distance<D>> List<QueryResult<D>> reverseKNNQuery(O object,
                                                                             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.

Parameters:

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

bulkKNNQueryForIDs

public abstract <D extends Distance<D>> List<List<QueryResult<D>>> bulkKNNQueryForIDs(List<Integer> ids,
                                                                                      int k,
                                                                                      SpatialDistanceFunction<O,D> distanceFunction)

Performs a bulk k-nearest neighbor query for the given object IDs. The query result is in ascending order to the distance to the query objects.

Parameters:

ids - 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 the query results

getLeaves

public abstract List<E> getLeaves()

Returns a list of entries pointing to the leaf nodes of this spatial index.

Returns:

a list of entries pointing to the leaf nodes of this spatial index