Package elki.index.tree.spatial.rstarvariants

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

  • Type Parameters:
    N - Node type
    E - Entry type
    S - Settings container
    All Implemented Interfaces:
    Index
    Direct Known Subclasses:
    FlatRStarTree, NonFlatRStarTree
    public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N,​E>,​E extends SpatialEntry,​S extends RTreeSettings>
extends IndexTree<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

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

      • 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)
        Add a new leaf entry to the tree.
        Parameters:
        leaf - Leaf entry

      • insertEntry

        protected void insertEntry​(E entry,
                           int depth)
        Inserts the specified entry at the specified level into this R*-Tree.
        Parameters:
        entry - the entry to be inserted
        depth - the depth at which the 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

      • 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.ArrayDeque<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()
        Returns a list of entries pointing to the leaf entries of this spatial index.
        Returns:
        a list of entries pointing to the leaf entries of this spatial index

      • getLeafNodeEntries

        private void getLeafNodeEntries​(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 interface: Index
        Send statistics to the logger, if enabled.

        Note: you must have set the logging level appropriately before initializing the index! Otherwise, the index might not have collected the desired statistics.

        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()
        Overrides:
        toString in class java.lang.Object