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.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>
- Type Parameters:
O
- Object typeN
- Node typeE
- Entry type
- All Implemented Interfaces:
- Index<O>, 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_ID, cacheSize, dirCapacity, dirMinimum, file, FILE_ID, initialized, leafCapacity, leafMinimum, PAGE_SIZE_ID, 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 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, batchNN, bulkKNNQueryForIDs, choosePath, clearReinsertions, containedTest, createLeafNodes, createNewDirectoryEntry, createNewLeafEntry, createNewRoot, delete, doKNNQuery, findPathToObject, getHeight, getLeaves, getSortedEntries, getSortedEntries, getValues, initializeCapacities, initializeFromFile, insert, insert, insertDirectoryEntry, insertLeafEntry, kNNQuery, rangeQuery, rangeQuery, reInsert, reverseKNNQuery, setHeight, toString, union |
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex |
close, createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, getFileName, getLogicalPageAccess, getNode, getNode, getNodeClass, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, postDelete, preInsert, resetPageAccess |
NonFlatRStarTree
public NonFlatRStarTree(Parameterization config)
- Constructor, adhering to
Parameterizable
- Parameters:
config
- Parameterization
hasOverflow
protected boolean hasOverflow(N node)
- Returns true if in the specified node an overflow occurred, 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 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<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 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<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
bulkLoad
protected void bulkLoad(List<O> objects)
- 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<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