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.index.tree.TreeIndex<O,N,E>
          de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex<O,N,E>

Type Parameters:

O - Vector type

N - Node type

E - Entry type

All Implemented Interfaces:

Index<O>, 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.
private Flag	BULK_LOAD_FLAG Parameter for bulk loading
static OptionID	BULK_LOAD_ID OptionID for BULK_LOAD_FLAG
static OptionID	BULK_LOAD_STRATEGY_ID OptionID for BULK_LOAD_STRATEGY_PARAM
private StringParameter	BULK_LOAD_STRATEGY_PARAM Parameter for bulk strategy
protected BulkSplit.Strategy	bulkLoadStrategy The strategy for bulk load.

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

CACHE_SIZE_ID, cacheSize, dirCapacity, dirMinimum, file, FILE_ID, initialized, leafCapacity, leafMinimum, PAGE_SIZE_ID, pageSize

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

debug, logger

Constructor Summary

SpatialIndex(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

abstract <D extends Distance<D>> List<List<DistanceResultPair<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<DistanceResultPair<D>>	kNNQuery(O obj, int k, SpatialDistanceFunction<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<DistanceResultPair<D>>	rangeQuery(O obj, D epsilon, SpatialDistanceFunction<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<DistanceResultPair<D>>	rangeQuery(O obj, String epsilon, SpatialDistanceFunction<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<DistanceResultPair<D>>	reverseKNNQuery(O object, int k, SpatialDistanceFunction<O,D> distanceFunction) Performs a reverse k-nearest neighbor query for the given object ID.
void	setDatabase(Database<O> database) Sets the database in the distance function of this index (if existing).

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

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

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

Methods inherited from interface de.lmu.ifi.dbs.elki.index.Index

delete, insert, insert

Field Detail

BULK_LOAD_ID

public static final OptionID BULK_LOAD_ID

OptionID for BULK_LOAD_FLAG

BULK_LOAD_FLAG

private final Flag BULK_LOAD_FLAG

Parameter for bulk loading

BULK_LOAD_STRATEGY_ID

public static final OptionID BULK_LOAD_STRATEGY_ID

OptionID for BULK_LOAD_STRATEGY_PARAM

BULK_LOAD_STRATEGY_PARAM

private final StringParameter BULK_LOAD_STRATEGY_PARAM

Parameter for bulk strategy

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(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

setDatabase

public void setDatabase(Database<O> database)

Sets the database 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<DistanceResultPair<D>> rangeQuery(O obj,
                                                                               String epsilon,
                                                                               SpatialDistanceFunction<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.

Type Parameters:

D - distance type

Parameters:

obj - 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 abstract <D extends Distance<D>> List<DistanceResultPair<D>> rangeQuery(O obj,
                                                                               D epsilon,
                                                                               SpatialDistanceFunction<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.

Type Parameters:

D - distance type

Parameters:

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

kNNQuery

public abstract <D extends Distance<D>> List<DistanceResultPair<D>> kNNQuery(O obj,
                                                                             int k,
                                                                             SpatialDistanceFunction<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.

Type Parameters:

D - distance type

Parameters:

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

reverseKNNQuery

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

Type Parameters:

D - distance type

Parameters:

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

bulkKNNQueryForIDs

public abstract <D extends Distance<D>> List<List<DistanceResultPair<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.

Type Parameters:

D - distance type

Parameters:

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