Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar
Class RStarTree<O extends NumberVector<O,?>>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      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>
                  extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,RStarTreeNode,SpatialEntry>
                      extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTree<O>
Type Parameters:
O - Object type
All Implemented Interfaces:
Index<O>, Parameterizable

@Title(value="R*-Tree")
@Description(value="Balanced index structure based on bounding rectangles.")
@Reference(authors="N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger",
           title="The R*-tree: an efficient and robust access method for points and rectangles",
           booktitle="Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990",
           url="http://dx.doi.org/10.1145/93597.98741")
public class RStarTree<O extends NumberVector<O,?>>
extends NonFlatRStarTree<O,RStarTreeNode,SpatialEntry>

RStarTree is a spatial index structure based on the concepts of the R*-Tree. Apart from organizing the objects it also provides several methods to search for certain object in the structure and ensures persistence.

Author:
Elke Achtert

Field Summary
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree
distanceCalcs, extraIntegrityChecks, height, reinsertions
 
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.logging.AbstractLoggable
debug, logger
 
Constructor Summary
RStarTree(Parameterization config)
          Constructor, adhering to Parameterizable
 
Method Summary
protected  SpatialEntry createNewDirectoryEntry(RStarTreeNode node)
          Creates a new directory entry representing the specified node.
protected  RStarTreeNode createNewDirectoryNode(int capacity)
          Creates a new directory node with the specified capacity.
protected  SpatialEntry createNewLeafEntry(O o)
          Creates a new leaf entry representing the specified data object in the specified subtree.
protected  RStarTreeNode createNewLeafNode(int capacity)
          Creates a new leaf node with the specified capacity.
protected  SpatialEntry createRootEntry()
          Creates an entry representing the root node.
protected  Class<RStarTreeNode> getNodeClass()
          Return the node base class.
protected  void postDelete(O o)
          Performs necessary operations after deleting the specified object.
protected  void preInsert(SpatialEntry entry)
          Performs necessary operations before inserting the specified entry.
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree
bulkLoad, computeHeight, createEmptyRoot, hasOverflow, hasUnderflow
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree
adjustTree, batchNN, bulkKNNQueryForIDs, choosePath, clearReinsertions, containedTest, createLeafNodes, createNewRoot, delete, doKNNQuery, findPathToObject, getHeight, getLeaves, getSortedEntries, getSortedEntries, getValues, initializeCapacities, initializeFromFile, insert, insert, insertDirectoryEntry, insertLeafEntry, kNNQuery, rangeQuery, rangeQuery, reInsert, reverseKNNQuery, setHeight, toString, union
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex
setDatabase
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
close, createHeader, getFileName, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, 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, wait, wait, wait
 

Constructor Detail

RStarTree

public RStarTree(Parameterization config)
Constructor, adhering to Parameterizable

Parameters:
config - Parameterization
Method Detail

createRootEntry

protected SpatialEntry createRootEntry()
Creates an entry representing the root node.

Specified by:
createRootEntry in class TreeIndex<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Returns:
an entry representing the root node

createNewLeafEntry

protected SpatialEntry createNewLeafEntry(O o)
Description copied from class: AbstractRStarTree
Creates a new leaf entry representing the specified data object in the specified subtree.

Specified by:
createNewLeafEntry in class AbstractRStarTree<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Parameters:
o - the data object to be represented by the new entry
Returns:
the newly created leaf entry

createNewDirectoryEntry

protected SpatialEntry createNewDirectoryEntry(RStarTreeNode node)
Description copied from class: AbstractRStarTree
Creates a new directory entry representing the specified node.

Specified by:
createNewDirectoryEntry in class AbstractRStarTree<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Parameters:
node - the node to be represented by the new entry
Returns:
the newly created directory entry

createNewLeafNode

protected RStarTreeNode createNewLeafNode(int capacity)
Creates a new leaf node with the specified capacity.

Specified by:
createNewLeafNode in class TreeIndex<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Parameters:
capacity - the capacity of the new node
Returns:
a new leaf node

createNewDirectoryNode

protected RStarTreeNode createNewDirectoryNode(int capacity)
Creates a new directory node with the specified capacity.

Specified by:
createNewDirectoryNode in class TreeIndex<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Parameters:
capacity - the capacity of the new node
Returns:
a new directory node

preInsert

protected void preInsert(SpatialEntry entry)
Performs necessary operations before inserting the specified entry.

Specified by:
preInsert in class TreeIndex<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Parameters:
entry - the entry to be inserted

postDelete

protected void postDelete(O o)
Performs necessary operations after deleting the specified object.

Specified by:
postDelete in class TreeIndex<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Parameters:
o - the object to be deleted

getNodeClass

protected Class<RStarTreeNode> getNodeClass()
Return the node base class.

Specified by:
getNodeClass in class TreeIndex<O extends NumberVector<O,?>,RStarTreeNode,SpatialEntry>
Returns:
node base class

Release 0.3 (2010-03-31_1612)