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

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>
              de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>
                  de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,RStarTreeNode,SpatialEntry>
                      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