Package elki.index.tree.spatial.rstarvariants.strategies.overflow

Class LimitedReinsertOverflowTreatment

java.lang.Object

elki.index.tree.spatial.rstarvariants.strategies.overflow.LimitedReinsertOverflowTreatment

All Implemented Interfaces:

OverflowTreatment

@Reference(authors="Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger",
           title="The R*-tree: an efficient and robust access method for points and rectangles",
           booktitle="Proc. 1990 ACM SIGMOD Int. Conf. Management of Data",
           url="https://doi.org/10.1145/93597.98741",
           bibkey="DBLP:conf/sigmod/BeckmannKSS90")
public class LimitedReinsertOverflowTreatment
extends java.lang.Object
implements OverflowTreatment

Limited reinsertions, as proposed by the R*-Tree: For each real insert, allow reinsertions to happen only once per level.

Reference:

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger
The R*-tree: an efficient and robust access method for points and rectangles
Proc. 1990 ACM SIGMOD Int. Conf. Management of Data

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LimitedReinsertOverflowTreatment.Par	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
private long[]	reinsertions	Bitset to keep track of levels a reinsert has been performed at.
private ReinsertStrategy	reinsertStrategy	Strategy for the actual reinsertions
static LimitedReinsertOverflowTreatment	RSTAR_OVERFLOW	Default insert strategy used by R*-tree

Constructor Summary

Constructors

Constructor	Description
LimitedReinsertOverflowTreatment(ReinsertStrategy reinsertStrategy)	Constructor.

Method Summary

Modifier and Type	Method	Description
<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry> boolean	handleOverflow(AbstractRStarTree<N,E,?> tree, N node, IndexTreePath<E> path)	Handle overflow in the given node.
void	reinitialize()	Reinitialize the reinsertion treatment (for a new primary insertion).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

RSTAR_OVERFLOW

public static final LimitedReinsertOverflowTreatment RSTAR_OVERFLOW

Default insert strategy used by R*-tree

reinsertions

private long[] reinsertions

Bitset to keep track of levels a reinsert has been performed at.

reinsertStrategy

private final ReinsertStrategy reinsertStrategy

Strategy for the actual reinsertions

Constructor Detail

LimitedReinsertOverflowTreatment

public LimitedReinsertOverflowTreatment(ReinsertStrategy reinsertStrategy)

Constructor.

Parameters:

reinsertStrategy - Reinsertion strategy

Method Detail

handleOverflow

public <N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N,E,?> tree,
                                                                                                        N node,
                                                                                                        IndexTreePath<E> path)

Description copied from interface: OverflowTreatment

Handle overflow in the given node.

Specified by:

handleOverflow in interface OverflowTreatment

Type Parameters:

N - Node

E - Entry

Parameters:

tree - Tree

node - Node

path - Path

Returns:

true when already handled (e.g., by reinserting)

reinitialize

public void reinitialize()

Description copied from interface: OverflowTreatment

Reinitialize the reinsertion treatment (for a new primary insertion).

Specified by:

reinitialize in interface OverflowTreatment