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

Class NonFlatRStarTree<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>

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

Type Parameters:

N - Node type

E - Entry type

All Implemented Interfaces:

Index, Result

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 de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

AbstractRStarTree.Statistics

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

EXTRA_INTEGRITY_CHECKS, height, lastInsertedEntry, settings, statistics

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and 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 de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

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

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

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

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)

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)

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

Computes the height of this RTree. Is called by the constructor. and should be overwritten by subclasses if necessary.

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)

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