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

java.lang.Object
  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<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

Release 0.4.0 (2011-09-20_1324)