Package elki.index.tree.spatial.rstarvariants.flat

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

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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

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 file

settings - 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 class AbstractRStarTree<FlatRStarTreeNode,SpatialEntry,RTreeSettings>

Parameters:

header - File header

file - Page file

getNode

public FlatRStarTreeNode getNode(int nodeID)

Description copied from class: IndexTree

Returns the node with the specified id.

Overrides:

getNode in class IndexTree<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 class AbstractRStarTree<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 class AbstractRStarTree<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 class IndexTree<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 class AbstractRStarTree<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 class AbstractRStarTree<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 class IndexTree<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 class IndexTree<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 class AbstractRStarTree<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 class IndexTree<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 class IndexTree<FlatRStarTreeNode,SpatialEntry>

Returns:

the static logger