de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants
Class NonFlatRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

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

Type Parameters:

N - Node type

E - Entry type

Direct Known Subclasses:

DeLiCluTree, RStarTree

public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
extends AbstractRStarTree<N,E>

Abstract superclass for all non-flat R*-Tree variants.

Field Summary

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

bulkSplitter, distanceCalcs, extraIntegrityChecks, height, insertionStrategy, lastInsertedEntry, nodeSplitter, reinsertions

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

NonFlatRStarTree(PageFile<N> pagefile, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy)
Constructor.

Method Summary

protected void	bulkLoad(List<E> spatialObjects) Performs a bulk load on this RTree with the specified data.
protected int	computeHeight() Computes the height of this RTree.
private List<N>	createDirectoryNodes(List<N> nodes) Creates and returns the directory nodes for bulk load.
protected void	createEmptyRoot(E exampleLeaf) Creates an empty root node and writes it to file.
private N	createRoot(N root, List<? extends SpatialComparable> objects) Returns a root node for bulk load.
protected boolean	hasOverflow(N node) Returns true if in the specified node an overflow occurred, false otherwise.
protected boolean	hasUnderflow(N node) Returns true if in the specified node an underflow occurred, false otherwise.

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

adjustTree, canBulkLoad, choosePath, clearReinsertions, containedTest, createBulkLeafNodes, createNewDirectoryEntry, 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, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, 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

Constructor Detail

NonFlatRStarTree

public NonFlatRStarTree(PageFile<N> pagefile,
                        BulkSplit bulkSplitter,
                        InsertionStrategy insertionStrategy)

Constructor.

Parameters:

pagefile - Page file

bulkSplitter - bulk load strategy

insertionStrategy - the strategy to find the child to insert to

Method Detail

hasOverflow

protected boolean hasOverflow(N node)

Returns true if in the specified node an overflow occurred, false otherwise.

Specified by:

hasOverflow in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

node - the node to be tested for overflow

Returns:

true if in the specified node an overflow occurred, false otherwise

hasUnderflow

protected boolean hasUnderflow(N node)

Returns true if in the specified node an underflow occurred, false otherwise.

Specified by:

hasUnderflow in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

node - the node to be tested for underflow

Returns:

true if in the specified node an underflow occurred, false otherwise

computeHeight

protected int computeHeight()

Computes the height of this RTree. Is called by the constructor. and should be overwritten by subclasses if necessary.

Specified by:

computeHeight in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Returns:

the height of this RTree

createEmptyRoot

protected void createEmptyRoot(E exampleLeaf)

Description copied from class: IndexTree

Creates an empty root node and writes it to file.

Specified by:

createEmptyRoot in class IndexTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

bulkLoad

protected void bulkLoad(List<E> spatialObjects)

Performs a bulk load on this RTree with the specified data. Is called by the constructor and should be overwritten by subclasses if necessary.

Specified by:

bulkLoad in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

createDirectoryNodes

private List<N> createDirectoryNodes(List<N> nodes)

Creates and returns the directory nodes for bulk load.

Parameters:

nodes - the nodes to be inserted

Returns:

the directory nodes containing the nodes

createRoot

private N createRoot(N root,
                     List<? extends SpatialComparable> objects)

Returns a root node for bulk load. If the objects are data objects a leaf node will be returned, if the objects are nodes a directory node will be returned.

Parameters:

root - the new root node

objects - the spatial objects to be inserted

Returns:

the root node