Package | Description |
---|---|
de.lmu.ifi.dbs.elki.index.tree |
Tree-based index structures
|
de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants |
M-Tree and variants.
|
de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants |
R*-Tree and variants.
|
de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow |
Overflow treatment strategies for R-Trees
|
Modifier and Type | Field and Description |
---|---|
private IndexTreePath<E> |
IndexTreePath.parentPath
Path representing the parent, null if lastPathComponent represents the
root.
|
Modifier and Type | Field and Description |
---|---|
Enumeration<IndexTreePath<E>> |
BreadthFirstEnumeration.EMPTY_ENUMERATION
Represents an empty enumeration.
|
private Queue<Enumeration<IndexTreePath<E>>> |
BreadthFirstEnumeration.queue
The queue for the enumeration.
|
Modifier and Type | Method and Description |
---|---|
IndexTreePath<E> |
IndexTreePath.getParentPath()
Returns a path containing all the elements of this object, except the last
path component.
|
IndexTreePath<E> |
IndexTree.getRootPath()
Returns the path to the root of this tree.
|
IndexTreePath<E> |
BreadthFirstEnumeration.nextElement()
Returns the next element of this enumeration if this enumeration object has
at least one more element to provide.
|
IndexTreePath<E> |
IndexTreePath.pathByAddingChild(TreeIndexPathComponent<E> child)
Returns a new path containing all the elements of this object plus
child . |
Modifier and Type | Method and Description |
---|---|
Enumeration<IndexTreePath<E>> |
Node.children(IndexTreePath<E> parentPath)
Returns an enumeration of the children paths of this node.
|
Enumeration<IndexTreePath<E>> |
AbstractNode.children(IndexTreePath<E> parentPath) |
Modifier and Type | Method and Description |
---|---|
Enumeration<IndexTreePath<E>> |
Node.children(IndexTreePath<E> parentPath)
Returns an enumeration of the children paths of this node.
|
Enumeration<IndexTreePath<E>> |
AbstractNode.children(IndexTreePath<E> parentPath) |
boolean |
IndexTreePath.isDescendant(IndexTreePath<E> aIndexPath)
Returns true if
aIndexPath is a descendant of this IndexPath. |
Constructor and Description |
---|
BreadthFirstEnumeration(IndexTree<N,E> index,
IndexTreePath<E> rootPath)
Creates a new breadth first enumeration with the specified node as root
node.
|
IndexTreePath(IndexTreePath<E> parent,
TreeIndexPathComponent<E> lastElement)
Constructs a new IndexPath, which is the path identified by
parent ending in lastElement . |
Modifier and Type | Method and Description |
---|---|
private IndexTreePath<E> |
AbstractMTree.choosePath(E object,
IndexTreePath<E> subtree)
Chooses the best path of the specified subtree for insertion of the given
object.
|
private IndexTreePath<E> |
AbstractMTree.createNewRoot(N oldRoot,
N newNode,
DBID firstRoutingObjectID,
DBID secondRoutingObjectID)
Creates a new root node that points to the two specified child nodes and
return the path to the new root.
|
Modifier and Type | Method and Description |
---|---|
private void |
AbstractMTree.adjustTree(IndexTreePath<E> subtree)
Adjusts the tree after insertion of some nodes.
|
private IndexTreePath<E> |
AbstractMTree.choosePath(E object,
IndexTreePath<E> subtree)
Chooses the best path of the specified subtree for insertion of the given
object.
|
Modifier and Type | Method and Description |
---|---|
protected IndexTreePath<E> |
AbstractRStarTree.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 IndexTreePath<E> |
AbstractRStarTree.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 IndexTreePath<E> |
AbstractRStarTree.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.
|
Modifier and Type | Method and Description |
---|---|
protected void |
AbstractRStarTree.adjustTree(IndexTreePath<E> subtree)
Adjusts the tree after insertion of some nodes.
|
protected IndexTreePath<E> |
AbstractRStarTree.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.
|
private void |
AbstractRStarTree.condenseTree(IndexTreePath<E> subtree,
Stack<N> stack)
Condenses the tree after deletion of some nodes.
|
protected void |
AbstractRStarTree.deletePath(IndexTreePath<E> deletionPath)
Delete a leaf at a given path - deletions for non-leaves are not supported!
|
protected IndexTreePath<E> |
AbstractRStarTree.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.
|
private N |
AbstractRStarTree.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 |
AbstractRStarTree.reInsert(N node,
IndexTreePath<E> path,
int[] offs)
Reinserts the specified node at the specified level.
|
Modifier and Type | Method and Description |
---|---|
<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry> |
OverflowTreatment.handleOverflow(AbstractRStarTree<N,E> tree,
N node,
IndexTreePath<E> path)
Handle overflow in the given node.
|
<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry> |
LimitedReinsertOverflowTreatment.handleOverflow(AbstractRStarTree<N,E> tree,
N node,
IndexTreePath<E> path) |
<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry> |
SplitOnlyOverflowTreatment.handleOverflow(AbstractRStarTree<N,E> tree,
N node,
IndexTreePath<E> path) |