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
de.lmu.ifi.dbs.elki.logging.AbstractLoggable
de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
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,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
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 |
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.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 |
NonFlatRStarTree
public NonFlatRStarTree()
- Creates a new RTree.
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 nodeobjects
- the spatial objects to be inserted
- Returns:
- the root node