Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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
  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.index.tree.TreeIndex<O,N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex<O,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>
All Implemented Interfaces:
Index<O>, Loggable, 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
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_D, BULK_LOAD_F, BULK_LOAD_STRATEGY_D, BULK_LOAD_STRATEGY_P, bulkLoadStrategy
 
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
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<QueryResult<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 obect from this index.
protected
<D extends Distance<D>>
void
doKNNQuery(Object object, DistanceFunction<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 occured, false otherwise.
protected abstract  boolean hasUnderflow(N node)
          Returns true if in the specified node an underflow occured, 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<QueryResult<D>>
kNNQuery(O object, int k, DistanceFunction<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<QueryResult<D>>
rangeQuery(O object, String epsilon, DistanceFunction<O,D> distanceFunction)
          Performs a range query for the given spatial objec 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<QueryResult<D>>
reverseKNNQuery(O object, int k, DistanceFunction<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, description, 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, 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, wait, wait, wait
 
Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription
 

Field Detail

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 obect 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<QueryResult<D>> rangeQuery(O object,
                                                               String epsilon,
                                                               DistanceFunction<O,D> distanceFunction)
Performs a range query for the given spatial objec 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>
Parameters:
object - 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 <D extends Distance<D>> List<QueryResult<D>> kNNQuery(O object,
                                                             int k,
                                                             DistanceFunction<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>
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 <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.

Specified by:
bulkKNNQueryForIDs in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
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

reverseKNNQuery

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

Specified by:
reverseKNNQuery in class SpatialIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
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

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
See Also:
TreeIndex.initializeCapacities(de.lmu.ifi.dbs.elki.data.DatabaseObject,boolean)

doKNNQuery

protected <D extends Distance<D>> void doKNNQuery(Object object,
                                                  DistanceFunction<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 beween 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 objcets

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 occured, false otherwise.

Parameters:
node - the node to be tested for overflow
Returns:
true if in the specified node an overflow occured, false otherwise

hasUnderflow

protected abstract boolean hasUnderflow(N node)
Returns true if in the specified node an underflow occured, false otherwise.

Parameters:
node - the node to be tested for underflow
Returns:
true if in the specified node an underflow occured, 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 occured
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

Release 0.1 (2008-07-10_1838)