de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants

Class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<N,E>

Type Parameters:

N - Node type

E - Entry type

Direct Known Subclasses:

NonFlatRStarTree

public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
extends SpatialIndexTree<N,E>

Abstract superclass for index structures based on a R*-Tree. Implementation Note: The restriction on NumberVector (as opposed to e.g. FeatureVector) is intentional, because we have spatial requirements.

Field Summary

Fields

Modifier and Type	Field and Description
protected BulkSplit	bulkSplitter The strategy for bulk load.
int	distanceCalcs For counting the number of distance computations.
protected static boolean	extraIntegrityChecks Development flag: This will enable some extra integrity checks on the tree.
protected int	height The height of this R*-Tree.
protected InsertionStrategy	insertionStrategy The insertion strategy to use
(package private) E	lastInsertedEntry The last inserted entry
protected SplitStrategy<? super E>	nodeSplitter The split strategy
protected Map<Integer,Boolean>	reinsertions Contains a boolean for each level of this R*-Tree that indicates if there was already a reinsert operation in this level during the current insert / delete operation.

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
AbstractRStarTree(PageFile<N> pagefile, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy) Constructor

Method Summary

Methods

Modifier and Type	Method and Description
protected void	adjustTree(IndexTreePath<E> subtree) Adjusts the tree after insertion of some nodes.
protected abstract void	bulkLoad(List<E> entrys) Performs a bulk load on this RTree with the specified data.
boolean	canBulkLoad() Test whether a bulk insert is still possible.
protected IndexTreePath<E>	choosePath(IndexTreePath<E> subtree, SpatialComparable mbr, int level) Chooses the best path of the specified subtree for insertion of the given mbr at the specified level.
protected void	clearReinsertions() Clears the reinsertions.
protected abstract int	computeHeight() Computes the height of this RTree.
private void	condenseTree(IndexTreePath<E> subtree, Stack<N> stack) Condenses the tree after deletion of some nodes.
protected TreeIndexPathComponent<E>	containedTest(N node, SpatialComparable mbr) Test on whether or not any child of node contains mbr.
protected List<N>	createBulkLeafNodes(List<E> objects) Creates and returns the leaf nodes for bulk load.
protected abstract E	createNewDirectoryEntry(N node) Creates a new directory entry representing the specified node.
protected IndexTreePath<E>	createNewRoot(N oldRoot, N newNode) Creates a new root node that points to the two specified child nodes and return the path to the new root.
protected void	deletePath(IndexTreePath<E> deletionPath) Delete a leaf at a given path - deletions for non-leaves are not supported!
void	doExtraIntegrityChecks() Perform additional integrity checks.
protected IndexTreePath<E>	findPathToObject(IndexTreePath<E> subtree, SpatialComparable mbr, DBID id) Returns the path to the leaf entry in the specified subtree that represents the data object with the specified mbr and id.
int	getHeight() Returns the height of this R*-Tree.
private void	getLeafNodes(N node, List<E> result, int currentLevel) Determines the entries pointing to the leaf nodes of the specified subtree
private TreeIndexPathComponent<E>	getLeastEnlargement(N node, SpatialComparable mbr) Returns the path information of the entry of the specified node with the least enlargement if the given mbr would be inserted into.
List<E>	getLeaves() Returns a list of entries pointing to the leaf entries of this spatial index.
protected abstract boolean	hasOverflow(N node) Returns true if in the specified node an overflow occurred, false otherwise.
protected abstract boolean	hasUnderflow(N node) Returns true if in the specified node an underflow occurred, false otherwise.
protected void	initializeCapacities(E exampleLeaf) Determines the maximum and minimum number of entries in a node.
void	initializeFromFile(TreeIndexHeader header, PageFile<N> file) Initializes this R*-Tree from an existing persistent file.
protected void	insertDirectoryEntry(E entry, int level) Inserts the specified directory entry at the specified level into this R*-Tree.
void	insertLeaf(E leaf) Add a new leaf entry to the tree.
protected void	insertLeafEntry(E entry) Inserts the specified leaf entry into this R*-Tree.
private N	overflowTreatment(N node, IndexTreePath<E> path) Treatment of overflow in the specified node: if the node is not the root node and this is the first call of overflowTreatment in the given level during insertion the specified node will be reinserted, otherwise the node will be split.
protected void	reInsert(N node, int level, IndexTreePath<E> path) Reinserts the specified node at the specified level.
protected void	setHeight(int height) Sets the height of this R*-Tree.
private N	split(N node) Splits the specified node and returns the newly created split node.
String	toString() Returns a string representation of this R*-Tree.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

createEmptyRoot, createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, 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

extraIntegrityChecks

protected static final boolean extraIntegrityChecks

Development flag: This will enable some extra integrity checks on the tree.

See Also:

Constant Field Values

reinsertions

protected final Map<Integer,Boolean> reinsertions

Contains a boolean for each level of this R*-Tree that indicates if there was already a reinsert operation in this level during the current insert / delete operation.

height

protected int height

The height of this R*-Tree.

distanceCalcs

public int distanceCalcs

For counting the number of distance computations.

lastInsertedEntry

E extends SpatialEntry lastInsertedEntry

The last inserted entry

bulkSplitter

protected BulkSplit bulkSplitter

The strategy for bulk load.

nodeSplitter

protected SplitStrategy<? super E extends SpatialEntry> nodeSplitter

The split strategy

insertionStrategy

protected final InsertionStrategy insertionStrategy

The insertion strategy to use

Constructor Detail

AbstractRStarTree

public AbstractRStarTree(PageFile<N> pagefile,
                 BulkSplit bulkSplitter,
                 InsertionStrategy insertionStrategy)

Constructor

Parameters:

pagefile - Page file

bulkSplitter - bulk load strategy

insertionStrategy - the strategy for finding the insertion candidate.

Method Detail

findPathToObject

protected IndexTreePath<E> findPathToObject(IndexTreePath<E> subtree,
                                SpatialComparable mbr,
                                DBID id)

Returns the path to the leaf entry in the specified subtree that represents the data object with the specified mbr and id.

Parameters:

subtree - the subtree to be tested

mbr - the mbr to look for

id - the id to look for

Returns:

the path to the leaf entry of the specified subtree that represents the data object with the specified mbr and id

insertLeaf

public void insertLeaf(E leaf)

Description copied from class: SpatialIndexTree

Add a new leaf entry to the tree.

Specified by:

insertLeaf in class SpatialIndexTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

leaf - Leaf entry

insertLeafEntry

protected void insertLeafEntry(E entry)

Inserts the specified leaf entry into this R*-Tree.

Parameters:

entry - the leaf entry to be inserted

insertDirectoryEntry

protected void insertDirectoryEntry(E entry,
                        int level)

Inserts the specified directory entry at the specified level into this R*-Tree.

Parameters:

entry - the directory entry to be inserted

level - the level at which the directory entry is to be inserted

deletePath

protected void deletePath(IndexTreePath<E> deletionPath)

Delete a leaf at a given path - deletions for non-leaves are not supported!

Parameters:

deletionPath - Path to delete

initializeFromFile

public void initializeFromFile(TreeIndexHeader header,
                      PageFile<N> file)

Initializes this R*-Tree from an existing persistent file.

Overrides:

initializeFromFile in class IndexTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

initializeCapacities

protected void initializeCapacities(E exampleLeaf)

Description copied from class: IndexTree

Determines the maximum and minimum number of entries in a node.

Specified by:

initializeCapacities in class IndexTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

canBulkLoad

public boolean canBulkLoad()

Test whether a bulk insert is still possible.

Returns:

Success code

createBulkLeafNodes

protected List<N> createBulkLeafNodes(List<E> objects)

Creates and returns the leaf nodes for bulk load.

Parameters:

objects - the objects to be inserted

Returns:

the array of leaf nodes containing the objects

bulkLoad

protected abstract void bulkLoad(List<E> entrys)

Performs a bulk load on this RTree with the specified data. Is called by the constructor.

getHeight

public final int getHeight()

Returns the height of this R*-Tree.

Returns:

the height of this R*-Tree

setHeight

protected void setHeight(int height)

Sets the height of this R*-Tree.

Parameters:

height - the height to be set

computeHeight

protected abstract int computeHeight()

Computes the height of this RTree. Is called by the constructor.

Returns:

the height of this RTree

clearReinsertions

protected void clearReinsertions()

Clears the reinsertions.

hasOverflow

protected abstract boolean hasOverflow(N node)

Returns true if in the specified node an overflow occurred, false otherwise.

Parameters:

node - the node to be tested for overflow

Returns:

true if in the specified node an overflow occurred, false otherwise

hasUnderflow

protected abstract boolean hasUnderflow(N node)

Returns true if in the specified node an underflow occurred, false otherwise.

Parameters:

node - the node to be tested for underflow

Returns:

true if in the specified node an underflow occurred, false otherwise

createNewDirectoryEntry

protected abstract E createNewDirectoryEntry(N node)

Creates a new directory entry representing the specified node.

Parameters:

node - the node to be represented by the new entry

Returns:

the newly created directory entry

createNewRoot

protected IndexTreePath<E> createNewRoot(N oldRoot,
                             N newNode)

Creates a new root node that points to the two specified child nodes and return the path to the new root.

Parameters:

oldRoot - the old root of this RTree

newNode - the new split node

Returns:

the path to the new root node that points to the two specified child nodes

containedTest

protected TreeIndexPathComponent<E> containedTest(N node,
                                      SpatialComparable mbr)

Test on whether or not any child of node contains mbr. If there are several containing children, the child with the minimum volume is chosen in order to get compact pages.

Parameters:

node - subtree

mbr - MBR to test for

Returns:

the child of node containing mbr with the minimum volume or null if none exists

choosePath

protected IndexTreePath<E> choosePath(IndexTreePath<E> subtree,
                          SpatialComparable mbr,
                          int level)

Chooses the best path of the specified subtree for insertion of the given mbr at the specified level.

Parameters:

subtree - the subtree to be tested for insertion

mbr - the mbr to be inserted

level - the level at which the mbr should be inserted (level 1 indicates leaf-level)

Returns:

the path of the appropriate subtree to insert the given mbr

getLeastEnlargement

private TreeIndexPathComponent<E> getLeastEnlargement(N node,
                                            SpatialComparable mbr)

Returns the path information of the entry of the specified node with the least enlargement if the given mbr would be inserted into.

Parameters:

node - the node which children have to be tested

mbr - the mbr of the node to be inserted

Returns:

the path information of the entry with the least enlargement if the given mbr would be inserted into

overflowTreatment

private N overflowTreatment(N node,
                  IndexTreePath<E> path)

Treatment of overflow in the specified node: if the node is not the root node and this is the first call of overflowTreatment in the given level during insertion the specified node will be reinserted, otherwise the node will be split.

Parameters:

node - the node where an overflow occurred

path - the path to the specified node

Returns:

the newly created split node in case of split, null in case of reinsertion

split

private N split(N node)

Splits the specified node and returns the newly created split node.

Parameters:

node - the node to be split

Returns:

the newly created split node

reInsert

protected void reInsert(N node,
            int level,
            IndexTreePath<E> path)

Reinserts the specified node at the specified level.

Parameters:

node - the node to be reinserted

level - the level of the node

path - the path to the node

adjustTree

protected void adjustTree(IndexTreePath<E> subtree)

Adjusts the tree after insertion of some nodes.

Parameters:

subtree - the subtree to be adjusted

condenseTree

private void condenseTree(IndexTreePath<E> subtree,
                Stack<N> stack)

Condenses the tree after deletion of some nodes.

Parameters:

subtree - the subtree to be condensed

stack - the stack holding the nodes to be reinserted after the tree has been condensed

getLeaves

public final List<E> getLeaves()

Description copied from class: SpatialIndexTree

Returns a list of entries pointing to the leaf entries of this spatial index.

Specified by:

getLeaves in class SpatialIndexTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Returns:

a list of entries pointing to the leaf entries of this spatial index

getLeafNodes

private void getLeafNodes(N node,
                List<E> result,
                int currentLevel)

Determines the entries pointing to the leaf nodes of the specified subtree

Parameters:

node - the subtree

result - the result to store the ids in

currentLevel - the level of the node in the R-Tree

doExtraIntegrityChecks

public void doExtraIntegrityChecks()

Perform additional integrity checks.

toString

public String toString()

Returns a string representation of this R*-Tree.

Overrides:

toString in class Object

Returns:

a string representation of this R*-Tree