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

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

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,S>

Type Parameters:

N - Node type

E - Entry type

All Implemented Interfaces:

Index, Result

Direct Known Subclasses:

FlatRStarTree, NonFlatRStarTree

public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry,S extends RTreeSettings>
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.

Since:

0.1

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	AbstractRStarTree.Statistics Class for tracking some statistics.

Field Summary

Fields

Modifier and Type	Field and Description
protected static boolean	EXTRA_INTEGRITY_CHECKS Development flag: This will enable some extra integrity checks on the tree.
protected int	height The height of this R*-Tree.
(package private) E	lastInsertedEntry The last inserted entry.
protected S	settings Settings class.
AbstractRStarTree.Statistics	statistics For counting the number of distance computations.

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, S settings) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	adjustTree(IndexTreePath<E> subtree) Adjusts the tree after insertion of some nodes.
protected abstract void	bulkLoad(java.util.List<E> entries) 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 depth, int cur) Chooses the best path of the specified subtree for insertion of the given mbr at the specified level.
protected abstract int	computeHeight() Computes the height of this RTree.
private void	condenseTree(IndexTreePath<E> subtree, java.util.Stack<N> stack) Condenses the tree after deletion of some nodes.
protected IndexTreePath<E>	containedTest(IndexTreePath<E> subtree, N node, SpatialComparable mbr) Test on whether or not any child of node contains mbr.
protected java.util.List<E>	createBulkLeafNodes(java.util.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, DBIDRef 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, java.util.List<E> result, int currentLevel) Determines the entries pointing to the leaf nodes of the specified subtree.
java.util.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 depth) 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.
void	logStatistics() Log some statistics, if enabled.
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.
void	reInsert(N node, IndexTreePath<E> path, int[] offs) 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.
java.lang.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, getDirMinimum, getFile, getLeafMinimum, getLogger, getNode, getNode, 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

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

getLongName, getShortName

Field Detail

EXTRA_INTEGRITY_CHECKS

protected static final boolean EXTRA_INTEGRITY_CHECKS

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

See Also:

Constant Field Values

height

protected int height

The height of this R*-Tree.

statistics

public AbstractRStarTree.Statistics statistics

For counting the number of distance computations.

lastInsertedEntry

E extends SpatialEntry lastInsertedEntry

The last inserted entry.

settings

protected S extends RTreeSettings settings

Settings class.

Constructor Detail

AbstractRStarTree

public AbstractRStarTree(PageFile<N> pagefile,
                         S settings)

Constructor.

Parameters:

pagefile - Page file

settings - Settings

Method Detail

findPathToObject

protected IndexTreePath<E> findPathToObject(IndexTreePath<E> subtree,
                                            SpatialComparable mbr,
                                            DBIDRef 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 depth)

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

Parameters:

entry - the directory entry to be inserted

depth - the depth 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. Initializes this index from an existing persistent file.

Overrides:

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

Parameters:

header - File header

file - Page file

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 java.util.List<E> createBulkLeafNodes(java.util.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(java.util.List<E> entries)

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

Parameters:

entries - Entries to bulk load

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

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 IndexTreePath<E> containedTest(IndexTreePath<E> subtree,
                                         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 depth,
                                      int cur)

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

depth - Reinsertion depth, 1 indicates root level

cur - Current depth

Returns:

the path of the appropriate subtree to insert the given mbr

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

public void reInsert(N node,
                     IndexTreePath<E> path,
                     int[] offs)

Reinserts the specified node at the specified level.

Parameters:

node - the node to be reinserted

path - the path to the node

offs - the nodes indexes to reinsert

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,
                          java.util.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 java.util.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,
                          java.util.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.

logStatistics

public void logStatistics()

Description copied from class: IndexTree

Log some statistics, if enabled.

Specified by:

logStatistics in interface Index

Overrides:

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

toString

public java.lang.String toString()

Returns a string representation of this R*-Tree.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this R*-Tree