Package elki.index.tree.spatial.rstarvariants

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

java.lang.Object

elki.index.tree.IndexTree<N,E>

elki.index.tree.spatial.rstarvariants.AbstractRStarTree<N,E,S>

elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<N,E,S>

Type Parameters:

N - Node type

E - Entry type

All Implemented Interfaces:

Index

Direct Known Subclasses:

DeLiCluTree, RdKNNTree, RStarTree

public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry,S extends RTreeSettings>
extends AbstractRStarTree<N,E,S>

Abstract superclass for all non-flat R*-Tree variants.

Since:

0.1

Author:

Elke Achtert

Nested Class Summary

Nested classes/interfaces inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree

AbstractRStarTree.Statistics

Field Summary

Fields inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree

EXTRA_INTEGRITY_CHECKS, height, lastInsertedEntry, settings, statistics

Fields inherited from class elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor	Description
NonFlatRStarTree(PageFile<N> pagefile, S settings)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected void	bulkLoad(java.util.List<E> spatialObjects)	Performs a bulk load on this RTree with the specified data.
protected int	computeHeight()	Computes the height of this RTree.
private java.util.List<E>	createBulkDirectoryNodes(java.util.List<E> nodes)	Creates and returns the directory nodes for bulk load.
protected void	createEmptyRoot(E exampleLeaf)	Creates an empty root node and writes it to file.
private N	createRoot(N root, java.util.List<E> 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 elki.index.tree.spatial.rstarvariants.AbstractRStarTree

adjustTree, canBulkLoad, choosePath, containedTest, createBulkLeafNodes, createNewDirectoryEntry, createNewRoot, deletePath, doExtraIntegrityChecks, findPathToObject, getHeight, getLeaves, initializeCapacities, initializeFromFile, insertEntry, insertLeaf, logStatistics, reInsert, setHeight, toString

Methods inherited from class elki.index.tree.IndexTree

createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, 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

Constructor Detail

NonFlatRStarTree

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

Constructor.

Parameters:

pagefile - Page file

settings - Settings

Method Detail

hasOverflow

protected boolean hasOverflow(N node)

Description copied from class: AbstractRStarTree

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

Specified by:

hasOverflow in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry,S extends 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(N node)

Description copied from class: AbstractRStarTree

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

Specified by:

hasUnderflow in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry,S extends RTreeSettings>

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()

Description copied from class: AbstractRStarTree

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

Specified by:

computeHeight in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry,S extends RTreeSettings>

Returns:

the height of this RTree

createEmptyRoot

protected void createEmptyRoot(E exampleLeaf)

Description copied from class: IndexTree

Creates an empty root node and writes it to file.

Specified by:

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

Parameters:

exampleLeaf - an object that will be stored in the index

bulkLoad

protected void bulkLoad(java.util.List<E> spatialObjects)

Description copied from class: AbstractRStarTree

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

Specified by:

bulkLoad in class AbstractRStarTree<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry,S extends RTreeSettings>

Parameters:

spatialObjects - Entries to bulk load

createBulkDirectoryNodes

private java.util.List<E> createBulkDirectoryNodes(java.util.List<E> 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,
                     java.util.List<E> 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 node

objects - the spatial objects to be inserted

Returns:

the root node