Class FlatRStarTree
- java.lang.Object
-
- elki.index.tree.IndexTree<N,E>
-
- elki.index.tree.spatial.rstarvariants.AbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
-
- elki.index.tree.spatial.rstarvariants.flat.FlatRStarTree
-
- All Implemented Interfaces:
Index
- Direct Known Subclasses:
FlatRStarTreeIndex
public abstract class FlatRStarTree extends AbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
FlatRTree is a spatial index structure based on a R*-Tree but with a flat directory. Apart from organizing the objects it also provides several methods to search for certain object in the structure and ensures persistence.- Since:
- 0.7.0
- Author:
- Elke Achtert
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree
AbstractRStarTree.Statistics
-
-
Field Summary
Fields Modifier and Type Field Description private static Logging
LOG
The logger for this class.private FlatRStarTreeNode
root
The root of this flat RTree.-
Fields inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree
EXTRA_INTEGRITY_CHECKS, height, settings, statistics
-
Fields inherited from class elki.index.tree.IndexTree
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
-
-
Constructor Summary
Constructors Constructor Description FlatRStarTree(PageFile<FlatRStarTreeNode> pagefile, RTreeSettings settings)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected void
bulkLoad(java.util.List<SpatialEntry> spatialObjects)
Performs a bulk load on this RTree with the specified data.protected int
computeHeight()
Computes the height of this RTree.protected void
createEmptyRoot(SpatialEntry exampleLeaf)
Creates an empty root node and writes it to file.protected SpatialEntry
createNewDirectoryEntry(FlatRStarTreeNode node)
Creates a new directory entry representing the specified node.protected FlatRStarTreeNode
createNewDirectoryNode()
Creates a new directory node with the specified capacity.protected FlatRStarTreeNode
createNewLeafNode()
Creates a new leaf node with the specified capacity.protected SpatialEntry
createRootEntry()
Creates an entry representing the root node.protected Logging
getLogger()
Get the (STATIC) logger for this class.FlatRStarTreeNode
getNode(int nodeID)
Returns the node with the specified id.protected boolean
hasOverflow(FlatRStarTreeNode node)
Returns true if in the specified node an overflow occurred, false otherwise.protected boolean
hasUnderflow(FlatRStarTreeNode node)
Returns true if in the specified node an underflow occurred, false otherwise.void
initializeFromFile(TreeIndexHeader header, PageFile<FlatRStarTreeNode> file)
Initializes this R*-Tree from an existing persistent file.-
Methods inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree
adjustTree, canBulkLoad, choosePath, containedTest, createBulkLeafNodes, createNewRoot, deletePath, doExtraIntegrityChecks, findPathToObject, getHeight, getLeaves, initializeCapacities, insertEntry, insertLeaf, logStatistics, reInsert, setHeight, toString
-
Methods inherited from class elki.index.tree.IndexTree
createHeader, deleteNode, getFile, getNode, getPageID, getPageSize, getRootEntry, getRootID, getRootPath, initialize, initialize, isRoot, postDelete, preInsert, writeNode
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
root
private FlatRStarTreeNode root
The root of this flat RTree.
-
-
Constructor Detail
-
FlatRStarTree
public FlatRStarTree(PageFile<FlatRStarTreeNode> pagefile, RTreeSettings settings)
Constructor.- Parameters:
pagefile
- Page filesettings
- Tree settings
-
-
Method Detail
-
initializeFromFile
public void initializeFromFile(TreeIndexHeader header, PageFile<FlatRStarTreeNode> file)
Description copied from class:AbstractRStarTree
Initializes this R*-Tree from an existing persistent file. Initializes this index from an existing persistent file.- Overrides:
initializeFromFile
in classAbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
- Parameters:
header
- File headerfile
- Page file
-
getNode
public FlatRStarTreeNode getNode(int nodeID)
Description copied from class:IndexTree
Returns the node with the specified id.- Overrides:
getNode
in classIndexTree<FlatRStarTreeNode,SpatialEntry>
- Parameters:
nodeID
- the page id of the node to be returned- Returns:
- the node with the specified id
-
computeHeight
protected int computeHeight()
Description copied from class:AbstractRStarTree
Computes the height of this RTree. Is called by the constructor.- Specified by:
computeHeight
in classAbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
- Returns:
- the height of this RTree
-
bulkLoad
protected void bulkLoad(java.util.List<SpatialEntry> 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 classAbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
- Parameters:
spatialObjects
- Entries to bulk load
-
createEmptyRoot
protected void createEmptyRoot(SpatialEntry exampleLeaf)
Description copied from class:IndexTree
Creates an empty root node and writes it to file.- Specified by:
createEmptyRoot
in classIndexTree<FlatRStarTreeNode,SpatialEntry>
- Parameters:
exampleLeaf
- an object that will be stored in the index
-
hasOverflow
protected boolean hasOverflow(FlatRStarTreeNode node)
Description copied from class:AbstractRStarTree
Returns true if in the specified node an overflow occurred, false otherwise.- Specified by:
hasOverflow
in classAbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
- 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(FlatRStarTreeNode node)
Description copied from class:AbstractRStarTree
Returns true if in the specified node an underflow occurred, false otherwise.- Specified by:
hasUnderflow
in classAbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
- Parameters:
node
- the node to be tested for underflow- Returns:
- true if in the specified node an underflow occurred, false otherwise
-
createNewLeafNode
protected FlatRStarTreeNode createNewLeafNode()
Description copied from class:IndexTree
Creates a new leaf node with the specified capacity.- Specified by:
createNewLeafNode
in classIndexTree<FlatRStarTreeNode,SpatialEntry>
- Returns:
- a new leaf node
-
createNewDirectoryNode
protected FlatRStarTreeNode createNewDirectoryNode()
Description copied from class:IndexTree
Creates a new directory node with the specified capacity.- Specified by:
createNewDirectoryNode
in classIndexTree<FlatRStarTreeNode,SpatialEntry>
- Returns:
- a new directory node
-
createNewDirectoryEntry
protected SpatialEntry createNewDirectoryEntry(FlatRStarTreeNode node)
Description copied from class:AbstractRStarTree
Creates a new directory entry representing the specified node.- Specified by:
createNewDirectoryEntry
in classAbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>
- Parameters:
node
- the node to be represented by the new entry- Returns:
- the newly created directory entry
-
createRootEntry
protected SpatialEntry createRootEntry()
Description copied from class:IndexTree
Creates an entry representing the root node.- Specified by:
createRootEntry
in classIndexTree<FlatRStarTreeNode,SpatialEntry>
- Returns:
- an entry representing the root node
-
getLogger
protected Logging getLogger()
Description copied from class:IndexTree
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classIndexTree<FlatRStarTreeNode,SpatialEntry>
- Returns:
- the static logger
-
-