Class RStarTree

  extended by de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>
      extended by de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndexTree<N,E>
          extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<RStarTreeNode,SpatialEntry>
                  extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTree
Direct Known Subclasses:

@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",
public class RStarTree
extends NonFlatRStarTree<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.

Field Summary
private static Logging logger
          The logger for this class.
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree
bulkSplitter, distanceCalcs, extraIntegrityChecks, height, insertionStrategy, nodeSplitter, reinsertions
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor Summary
RStarTree(PageFile<RStarTreeNode> pagefile, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy)
Method Summary
protected  SpatialEntry createNewDirectoryEntry(RStarTreeNode node)
          Creates a new directory entry representing the specified node.
protected  RStarTreeNode createNewDirectoryNode()
          Creates a new directory node with the specified capacity.
protected  RStarTreeNode createNewLeafNode()
          Creates a new leaf node with the specified capacity.
protected  SpatialEntry createRootEntry()
          Creates an entry representing the root node.
protected  Logging getLogger()
          Get the (STATIC) logger for this class.
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, canBulkLoad, choosePath, clearReinsertions, containedTest, createBulkLeafNodes, createNewRoot, deletePath, doExtraIntegrityChecks, findPathToObject, getHeight, getLeaves, initializeCapacities, initializeFromFile, insertDirectoryEntry, insertLeaf, insertLeafEntry, reInsert, setHeight, toString
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree
createHeader, deleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, isRoot, postDelete, preInsert, writeNode
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail


private static final Logging logger
The logger for this class.

Constructor Detail


public RStarTree(PageFile<RStarTreeNode> pagefile,
                 BulkSplit bulkSplitter,
                 InsertionStrategy insertionStrategy)

pagefile - Page file
bulkSplitter - bulk load strategy
insertionStrategy - the strategy to find the insertion child
Method Detail


protected SpatialEntry createRootEntry()
Description copied from class: IndexTree
Creates an entry representing the root node.

Specified by:
createRootEntry in class IndexTree<RStarTreeNode,SpatialEntry>
an entry representing the root node


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<RStarTreeNode,SpatialEntry>
node - the node to be represented by the new entry
the newly created directory entry


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

Specified by:
createNewLeafNode in class IndexTree<RStarTreeNode,SpatialEntry>
a new leaf node


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

Specified by:
createNewDirectoryNode in class IndexTree<RStarTreeNode,SpatialEntry>
a new directory node


protected Logging getLogger()
Description copied from class: IndexTree
Get the (STATIC) logger for this class.

Specified by:
getLogger in class IndexTree<RStarTreeNode,SpatialEntry>
the static logger

Release 0.4.0 (2011-09-20_1324)