de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar

Class RStarTree

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<N,E,S>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<RStarTreeNode,SpatialEntry,RTreeSettings>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTree

All Implemented Interfaces:

Index, Result

Direct Known Subclasses:

RStarTreeIndex

@Title(value="R*-Tree")
 @Description(value="Balanced index structure based on bounding rectangles.")
 @Reference(authors="Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger",
           title="The R*-tree: an efficient and robust access method for points and rectangles",
           booktitle="Proc. 1990 ACM SIGMOD Int. Conf. Management of Data",
           url="https://doi.org/10.1145/93597.98741",
           bibkey="DBLP:conf/sigmod/BeckmannKSS90")
public abstract class RStarTree
extends NonFlatRStarTree<RStarTreeNode,SpatialEntry,RTreeSettings>

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.

Reference:

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger
The R*-tree: an efficient and robust access method for points and rectangles
Proc. 1990 ACM SIGMOD Int. Conf. Management of Data

Since:

0.1

Author:

Elke Achtert

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

AbstractRStarTree.Statistics

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG The logger for this class.

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

EXTRA_INTEGRITY_CHECKS, height, settings, statistics

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
RStarTree(PageFile<RStarTreeNode> pagefile, RTreeSettings settings) Constructor.

Method Summary

Modifier and Type	Method and Description
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, containedTest, createBulkLeafNodes, createNewRoot, deletePath, doExtraIntegrityChecks, findPathToObject, getHeight, getLeaves, initializeCapacities, initializeFromFile, insertDirectoryEntry, insertLeaf, insertLeafEntry, logStatistics, reInsert, setHeight, toString

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

createHeader, deleteNode, getDirMinimum, getFile, getLeafMinimum, getNode, getNode, 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

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

getLongName, getShortName

Field Detail

LOG

private static final Logging LOG

The logger for this class.

Constructor Detail

RStarTree

public RStarTree(PageFile<RStarTreeNode> pagefile,
                 RTreeSettings settings)

Constructor.

Parameters:

pagefile - Page file

settings - Settings class

Method Detail

createRootEntry

protected SpatialEntry createRootEntry()

Description copied from class: IndexTree

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<RStarTreeNode,SpatialEntry>

Returns:

an entry representing the root node

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<RStarTreeNode,SpatialEntry,RTreeSettings>

Parameters:

node - the node to be represented by the new entry

Returns:

the newly created directory entry

createNewLeafNode

protected RStarTreeNode createNewLeafNode()

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<RStarTreeNode,SpatialEntry>

Returns:

a new leaf node

createNewDirectoryNode

protected RStarTreeNode createNewDirectoryNode()

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<RStarTreeNode,SpatialEntry>

Returns:

a new directory node

getLogger

protected Logging getLogger()

Description copied from class: IndexTree

Get the (STATIC) logger for this class.

Specified by:

getLogger in class IndexTree<RStarTreeNode,SpatialEntry>

Returns:

the static logger