de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants
Class AbstractRStarTree<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<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>
                  de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>

Type Parameters:

O - Object type

N - Node type

E - Entry type

All Implemented Interfaces:

Index<O>, Parameterizable

Direct Known Subclasses:

NonFlatRStarTree

public abstract class AbstractRStarTree<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
extends SpatialIndex<O,N,E>

Abstract superclass for index structures based on a R*-Tree.

Author:

Elke Achtert

Field Summary

protected static boolean	extraIntegrityChecks
private int	height The height of this R*-Tree.
private Map<Integer,Boolean>	reinsertions Contains a boolean for each level of this R*-Tree that indicates if there was already a reinsert operation in this level during the current insert / delete operation.

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

bulk, BULK_LOAD_ID, BULK_LOAD_STRATEGY_ID, bulkLoadStrategy

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.utilities.optionhandling.AbstractParameterizable

optionHandler

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

debug, logger

Constructor Summary

AbstractRStarTree()

Method Summary

private void	adjustTree(TreeIndexPath<E> subtree) Adjusts the tree after insertion of some nodes.
protected <D extends Distance<D>> void	batchNN(N node, SpatialDistanceFunction<O,D> distanceFunction, Map<Integer,KNNList<D>> knnLists) Performs a batch knn query.
<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.
protected abstract void	bulkLoad(List<O> objects) Performs a bulk load on this RTree with the specified data.
private TreeIndexPath<E>	choosePath(TreeIndexPath<E> subtree, HyperBoundingBox mbr, int level) Chooses the best path of the specified subtree for insertion of the given mbr at the specified level.
protected void	clearReinsertions() Clears the reinsertions.
protected abstract int	computeHeight() Computes the height of this RTree.
private void	condenseTree(TreeIndexPath<E> subtree, Stack<N> stack) Condenses the tree after deletion of some nodes.
protected List<N>	createLeafNodes(List<O> objects) Creates and returns the leaf nodes for bulk load.
protected abstract E	createNewDirectoryEntry(N node) Creates a new directory entry representing the specified node.
protected abstract E	createNewLeafEntry(O object) Creates a new leaf entry representing the specified data object in the specified subtree.
private TreeIndexPath<E>	createNewRoot(N oldRoot, N newNode) Creates a new root node that points to the two specified child nodes and return the path to the new root.
boolean	delete(O object) Deletes the specified object from this index.
protected <D extends Distance<D>> void	doKNNQuery(Object object, SpatialDistanceFunction<O,D> distanceFunction, KNNList<D> knnList) Performs a k-nearest neighbor query for the given NumberVector with the given parameter k and the according distance function.
protected TreeIndexPath<E>	findPathToObject(TreeIndexPath<E> subtree, HyperBoundingBox mbr, int id) Returns the path to the leaf entry in the specified subtree that represents the data object with the specified mbr and id.
private TreeIndexPathComponent<E>	getChildWithLeastOverlap(N node, HyperBoundingBox mbr) Returns the path information of the entry of the specified node which needs least overlap enlargement if the given mbr would be inserted into.
int	getHeight() Returns the height of this R*-Tree.
private void	getLeafNodes(N node, List<E> result, int currentLevel) Determines the entries pointing to the leaf nodes of the specified subtree
private TreeIndexPathComponent<E>	getLeastEnlargement(N node, HyperBoundingBox mbr) Returns the path information of the entry of the specified node with the least enlargement if the given mbr would be inserted into.
List<E>	getLeaves() Returns a list of entries pointing to the leaf nodes of this spatial index.
protected <D extends Distance<D>> List<DistanceEntry<D,E>>	getSortedEntries(N node, Collection<Integer> ids, SpatialDistanceFunction<O,D> distanceFunction) Sorts the entries of the specified node according to their minimum distance to the specified objects.
protected <D extends Distance<D>> List<DistanceEntry<D,E>>	getSortedEntries(N node, Integer q, SpatialDistanceFunction<O,D> distanceFunction) Sorts the entries of the specified node according to their minimum distance to the specified object.
protected double[]	getValues(O object) Returns a double array consisting of the values of the specified real vector.
protected abstract boolean	hasOverflow(N node) Returns true if in the specified node an overflow occurred, false otherwise.
protected abstract boolean	hasUnderflow(N node) Returns true if in the specified node an underflow occurred, false otherwise.
protected void	initializeCapacities(O object, boolean verbose) Determines the maximum and minimum number of entries in a node.
protected void	initializeFromFile() Initializes this R*-Tree from an existing persistent file.
void	insert(List<O> objects) Inserts the specified objects into this index.
void	insert(O object) Inserts the specified reel vector object into this index.
private void	insertDirectoryEntry(E entry, int level) Inserts the specified directory entry at the specified level into this R*-Tree.
private void	insertLeafEntry(E entry) Inserts the specified leaf entry into this R*-Tree.
<D extends Distance<D>> List<DistanceResultPair<D>>	kNNQuery(O object, int k, SpatialDistanceFunction<O,D> distanceFunction) Performs a k-nearest neighbor query for the given NumberVector with the given parameter k and the according distance function.
private N	overflowTreatment(N node, TreeIndexPath<E> path) Treatment of overflow in the specified node: if the node is not the root node and this is the first call of overflowTreatment in the given level during insertion the specified node will be reinserted, otherwise the node will be splitted.
<D extends Distance<D>> List<DistanceResultPair<D>>	rangeQuery(O object, String epsilon, SpatialDistanceFunction<O,D> distanceFunction) Performs a range query for the given spatial object with the given epsilon range and the according distance function.
private void	reInsert(N node, int level, TreeIndexPath<E> path) Reinserts the specified node at the specified level.
<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.
protected void	setHeight(int height) Sets the height of this R*-Tree.
private N	split(N node) Splits the specified node and returns the newly created split node.
String	toString() Returns a string representation of this RTree.
private HyperBoundingBox	union(HyperBoundingBox mbr1, HyperBoundingBox mbr2) Returns the union of the two specified MBRs.

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

setDatabase, setParameters

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

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

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

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

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, shortDescription

Field Detail

extraIntegrityChecks

protected static final boolean extraIntegrityChecks

See Also:

Constant Field Values

reinsertions

private final Map<Integer,Boolean> reinsertions

Contains a boolean for each level of this R*-Tree that indicates if there was already a reinsert operation in this level during the current insert / delete operation.

height

private int height

The height of this R*-Tree.

Constructor Detail

AbstractRStarTree

public AbstractRStarTree()

Method Detail

insert

public final void insert(O object)

Inserts the specified reel vector object into this index.

Parameters:

object - the vector to be inserted

insert

public final void insert(List<O> objects)

Inserts the specified objects into this index. If a bulk load mode is implemented, the objects are inserted in one bulk.

Parameters:

objects - the objects to be inserted

insertLeafEntry

private void insertLeafEntry(E entry)

Inserts the specified leaf entry into this R*-Tree.

Parameters:

entry - the leaf entry to be inserted

insertDirectoryEntry

private void insertDirectoryEntry(E entry,
                                  int level)

Inserts the specified directory entry at the specified level into this R*-Tree.

Parameters:

entry - the directory entry to be inserted

level - the level at which the directory entry is to be inserted

delete

public final boolean delete(O object)

Deletes the specified object from this index.

Parameters:

object - the object to be deleted

Returns:

true if this index did contain the object with the specified id, false otherwise

rangeQuery

public <D extends Distance<D>> List<DistanceResultPair<D>> rangeQuery(O object,
                                                                      String epsilon,
                                                                      SpatialDistanceFunction<O,D> distanceFunction)

Performs a range query for the given spatial 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.

Specified by:

rangeQuery in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Type Parameters:

D - distance type

Parameters:

object - 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 <D extends Distance<D>> List<DistanceResultPair<D>> kNNQuery(O object,
                                                                    int k,
                                                                    SpatialDistanceFunction<O,D> distanceFunction)

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

Specified by:

kNNQuery in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

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

Specified by:

bulkKNNQueryForIDs in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

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

reverseKNNQuery

public <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.

Specified by:

reverseKNNQuery in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

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

getLeaves

public final List<E> getLeaves()

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

Specified by:

getLeaves in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Returns:

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

getHeight

public final int getHeight()

Returns the height of this R*-Tree.

Returns:

the height of this R*-Tree

toString

public String toString()

Returns a string representation of this RTree.

Overrides:

toString in class Object

Returns:

a string representation of this RTree

initializeFromFile

protected void initializeFromFile()

Initializes this R*-Tree from an existing persistent file.

Overrides:

initializeFromFile in class TreeIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

initializeCapacities

protected void initializeCapacities(O object,
                                    boolean verbose)

Description copied from class: TreeIndex

Determines the maximum and minimum number of entries in a node.

Specified by:

initializeCapacities in class TreeIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

doKNNQuery

protected <D extends Distance<D>> void doKNNQuery(Object object,
                                                  SpatialDistanceFunction<O,D> distanceFunction,
                                                  KNNList<D> knnList)

Performs a k-nearest neighbor query for the given NumberVector 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:

object - the query object

distanceFunction - the distance function that computes the distances between the objects

knnList - the knn list containing the result

batchNN

protected <D extends Distance<D>> void batchNN(N node,
                                               SpatialDistanceFunction<O,D> distanceFunction,
                                               Map<Integer,KNNList<D>> knnLists)

Performs a batch knn query.

Parameters:

node - the node for which the query should be performed

distanceFunction - the distance function for computing the distances

knnLists - a map containing the knn lists for each query objects

findPathToObject

protected TreeIndexPath<E> findPathToObject(TreeIndexPath<E> subtree,
                                            HyperBoundingBox mbr,
                                            int id)

Returns the path to the leaf entry in the specified subtree that represents the data object with the specified mbr and id.

Parameters:

subtree - the subtree to be tested

mbr - the mbr to look for

id - the id to look for

Returns:

the path to the leaf entry of the specified subtree that represents the data object with the specified mbr and id

createLeafNodes

protected List<N> createLeafNodes(List<O> objects)

Creates and returns the leaf nodes for bulk load.

Parameters:

objects - the objects to be inserted

Returns:

the array of leaf nodes containing the objects

getSortedEntries

protected <D extends Distance<D>> List<DistanceEntry<D,E>> getSortedEntries(N node,
                                                                            Integer q,
                                                                            SpatialDistanceFunction<O,D> distanceFunction)

Sorts the entries of the specified node according to their minimum distance to the specified object.

Parameters:

node - the node

q - the id of the object

distanceFunction - the distance function for computing the distances

Returns:

a list of the sorted entries

getSortedEntries

protected <D extends Distance<D>> List<DistanceEntry<D,E>> getSortedEntries(N node,
                                                                            Collection<Integer> ids,
                                                                            SpatialDistanceFunction<O,D> distanceFunction)

Sorts the entries of the specified node according to their minimum distance to the specified objects.

Parameters:

node - the node

ids - the id of the objects

distanceFunction - the distance function for computing the distances

Returns:

a list of the sorted entries

getValues

protected double[] getValues(O object)

Returns a double array consisting of the values of the specified real vector.

Parameters:

object - the real vector

Returns:

a double array consisting of the values of the specified real vector

setHeight

protected void setHeight(int height)

Sets the height of this R*-Tree.

Parameters:

height - the height to be set

clearReinsertions

protected void clearReinsertions()

Clears the reinsertions.

hasOverflow

protected abstract boolean hasOverflow(N node)

Returns true if in the specified node an overflow occurred, false otherwise.

Parameters:

node - the node to be tested for overflow

Returns:

true if in the specified node an overflow occurred, false otherwise

hasUnderflow

protected abstract boolean hasUnderflow(N node)

Returns true if in the specified node an underflow occurred, false otherwise.

Parameters:

node - the node to be tested for underflow

Returns:

true if in the specified node an underflow occurred, false otherwise

computeHeight

protected abstract int computeHeight()

Computes the height of this RTree. Is called by the constructor.

Returns:

the height of this RTree

bulkLoad

protected abstract void bulkLoad(List<O> objects)

Performs a bulk load on this RTree with the specified data. Is called by the constructor.

Parameters:

objects - the data objects to be indexed

createNewLeafEntry

protected abstract E createNewLeafEntry(O object)

Creates a new leaf entry representing the specified data object in the specified subtree.

Parameters:

object - the data object to be represented by the new entry

Returns:

the newly created leaf entry

createNewDirectoryEntry

protected abstract E createNewDirectoryEntry(N node)

Creates a new directory entry representing the specified node.

Parameters:

node - the node to be represented by the new entry

Returns:

the newly created directory entry

choosePath

private TreeIndexPath<E> choosePath(TreeIndexPath<E> subtree,
                                    HyperBoundingBox mbr,
                                    int level)

Chooses the best path of the specified subtree for insertion of the given mbr at the specified level.

Parameters:

subtree - the subtree to be tested for insertion

mbr - the mbr to be inserted

level - the level at which the mbr should be inserted (level 1 indicates leaf-level)

Returns:

the path of the appropriate subtree to insert the given mbr

getLeastEnlargement

private TreeIndexPathComponent<E> getLeastEnlargement(N node,
                                                      HyperBoundingBox mbr)

Returns the path information of the entry of the specified node with the least enlargement if the given mbr would be inserted into.

Parameters:

node - the node which children have to be tested

mbr - the mbr of the node to be inserted

Returns:

the path information of the entry with the least enlargement if the given mbr would be inserted into

getChildWithLeastOverlap

private TreeIndexPathComponent<E> getChildWithLeastOverlap(N node,
                                                           HyperBoundingBox mbr)

Returns the path information of the entry of the specified node which needs least overlap enlargement if the given mbr would be inserted into.

Parameters:

node - the node of which the children should be tested

mbr - the mbr to be inserted into the children

Returns:

the path information of the entry which needs least overlap enlargement if the given mbr would be inserted into

union

private HyperBoundingBox union(HyperBoundingBox mbr1,
                               HyperBoundingBox mbr2)

Returns the union of the two specified MBRs.

Parameters:

mbr1 - the first MBR

mbr2 - the second MBR

Returns:

the union of the two specified MBRs

overflowTreatment

private N overflowTreatment(N node,
                            TreeIndexPath<E> path)

Treatment of overflow in the specified node: if the node is not the root node and this is the first call of overflowTreatment in the given level during insertion the specified node will be reinserted, otherwise the node will be splitted.

Parameters:

node - the node where an overflow occurred

path - the path to the specified node

Returns:

the newly created split node in case of split, null in case of reinsertion

split

private N split(N node)

Splits the specified node and returns the newly created split node.

Parameters:

node - the node to be splitted

Returns:

the newly created split node

reInsert

private void reInsert(N node,
                      int level,
                      TreeIndexPath<E> path)

Reinserts the specified node at the specified level.

Parameters:

node - the node to be reinserted

level - the level of the node

path - the path to the node

adjustTree

private void adjustTree(TreeIndexPath<E> subtree)

Adjusts the tree after insertion of some nodes.

Parameters:

subtree - the subtree to be adjusted

condenseTree

private void condenseTree(TreeIndexPath<E> subtree,
                          Stack<N> stack)

Condenses the tree after deletion of some nodes.

Parameters:

subtree - the subtree to be condensed

stack - the stack holding the nodes to be reinserted after the tree has been condensed

getLeafNodes

private void getLeafNodes(N node,
                          List<E> result,
                          int currentLevel)

Determines the entries pointing to the leaf nodes of the specified subtree

Parameters:

node - the subtree

result - the result to store the ids in

currentLevel - the level of the node in the R-Tree

createNewRoot

private TreeIndexPath<E> createNewRoot(N oldRoot,
                                       N newNode)

Creates a new root node that points to the two specified child nodes and return the path to the new root.

Parameters:

oldRoot - the old root of this RTree

newNode - the new split node

Returns:

the path to the new root node that points to the two specified child nodes