Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex<O,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>
                      extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,N,E>
All Implemented Interfaces:
Index<O>, Loggable, Parameterizable
Direct Known Subclasses:
DeLiCluTree, RdKNNTree, RStarTree

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

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

Author:
Elke Achtert

Field Summary
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex
bulk, BULK_LOAD_D, BULK_LOAD_F, BULK_LOAD_STRATEGY_D, BULK_LOAD_STRATEGY_P, bulkLoadStrategy
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
CACHE_SIZE_D, CACHE_SIZE_P, cacheSize, DEFAULT_CACHE_SIZE, DEFAULT_PAGE_SIZE, dirCapacity, dirMinimum, file, FILE_NAME_D, FILE_NAME_P, initialized, leafCapacity, leafMinimum, PAGE_SIZE_D, PAGE_SIZE_P, pageSize
 
Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
optionHandler
 
Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debug
 
Constructor Summary
NonFlatRStarTree()
          Creates a new RTree.
 
Method Summary
protected  void bulkLoad(List<O> objects)
          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(O object)
          Creates an empty root node and writes it to file.
private  N createRoot(N root, List<SpatialObject> objects)
          Returns a root node for bulk load.
protected  boolean hasOverflow(N node)
          Returns true if in the specified node an overflow occured, false otherwise.
protected  boolean hasUnderflow(N node)
          Returns true if in the specified node an underflow occured, false otherwise.
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree
batchNN, bulkKNNQueryForIDs, clearReinsertions, createLeafNodes, createNewDirectoryEntry, createNewLeafEntry, delete, doKNNQuery, findPathToObject, getHeight, getLeaves, getSortedEntries, getSortedEntries, getValues, initializeCapacities, initializeFromFile, insert, insert, kNNQuery, rangeQuery, reverseKNNQuery, setHeight, toString
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex
setDatabase, setParameters
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
close, createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, description, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, postDelete, preInsert, resetPageAccess
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, checkGlobalParameterConstraints, deleteOption, description, description, getAttributeSettings, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning
 
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.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription
 

Constructor Detail

NonFlatRStarTree

public NonFlatRStarTree()
Creates a new RTree.

Method Detail

hasOverflow

protected boolean hasOverflow(N node)
Returns true if in the specified node an overflow occured, false otherwise.

Specified by:
hasOverflow in class AbstractRStarTree<O extends NumberVector<O,?>,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 occured, false otherwise

hasUnderflow

protected boolean hasUnderflow(N node)
Returns true if in the specified node an underflow occured, false otherwise.

Specified by:
hasUnderflow in class AbstractRStarTree<O extends NumberVector<O,?>,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 occured, false otherwise

computeHeight

protected int computeHeight()
Computes the height of this RTree. Is called by the constructur. and should be overwritten by subclasses if necessary.

Specified by:
computeHeight in class AbstractRStarTree<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
Returns:
the height of this RTree

createEmptyRoot

protected void createEmptyRoot(O object)
Description copied from class: TreeIndex
Creates an empty root node and writes it to file.

Specified by:
createEmptyRoot in class TreeIndex<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
Parameters:
object - an object that will be stored in the index
See Also:
TreeIndex.createEmptyRoot(de.lmu.ifi.dbs.elki.data.DatabaseObject)

bulkLoad

protected void bulkLoad(List<O> objects)
Performs a bulk load on this RTree with the specified data. Is called by the constructur and should be overwritten by subclasses if necessary.

Specified by:
bulkLoad in class AbstractRStarTree<O extends NumberVector<O,?>,N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
Parameters:
objects - the data objects to be indexed

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<SpatialObject> 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.1 (2008-07-10_1838)