Class AbstractMTree<O,​N extends AbstractMTreeNode<O,​N,​E>,​E extends MTreeEntry,​S extends MTreeSettings<O,​N,​E>>

  • Type Parameters:
    O - the type of DatabaseObject to be stored in the metrical index
    N - the type of MetricalNode used in the metrical index
    E - the type of MetricalEntry used in the metrical index
    S - the type to store settings in.
    All Implemented Interfaces:
    Index
    Direct Known Subclasses:
    AbstractMkTree, MTree

    public abstract class AbstractMTree<O,​N extends AbstractMTreeNode<O,​N,​E>,​E extends MTreeEntry,​S extends MTreeSettings<O,​N,​E>>
    extends MetricalIndexTree<O,​N,​E>
    Abstract super class for all M-Tree variants.
    Since:
    0.1
    Author:
    Elke Achtert
    • Field Detail

      • EXTRA_INTEGRITY_CHECKS

        private static final boolean EXTRA_INTEGRITY_CHECKS
        Debugging flag: do extra integrity checks.
        See Also:
        Constant Field Values
    • Constructor Detail

      • AbstractMTree

        public AbstractMTree​(PageFile<N> pagefile,
                             S settings)
        Constructor.
        Parameters:
        pagefile - Page file
        settings - Tree settings
    • Method Detail

      • toString

        public java.lang.String toString()
        Returns a string representation of this M-Tree by performing a breadth first enumeration on the tree and adding the string representation of the visited nodes and their entries to the result.
        Overrides:
        toString in class java.lang.Object
        Returns:
        a string representation of this M-Tree
      • insert

        public void insert​(E entry,
                           boolean withPreInsert)
        Inserts the specified object into this M-Tree.
        Parameters:
        entry - the entry to be inserted
        withPreInsert - if this flag is true, the preInsert method will be called before inserting the object
      • insertAll

        public void insertAll​(java.util.List<E> entries)
        Bulk insert.
        Parameters:
        entries - Entries to insert
      • createEmptyRoot

        protected final 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 AbstractMTreeNode<O,​N,​E>,​E extends MTreeEntry>
        Parameters:
        exampleLeaf - an object that will be stored in the index
      • getSortedEntries

        protected final java.util.List<DoubleIntPair> getSortedEntries​(N node,
                                                                       DBID q)
        Sorts the entries of the specified node according to their minimum distance to the specified object.
        Parameters:
        node - the node
        q - the id of the object
        Returns:
        a list of the sorted entries
      • distance

        public abstract double distance​(DBIDRef id1,
                                        DBIDRef id2)
        Returns the distance between the two specified ids.
        Parameters:
        id1 - the first id
        id2 - the second id
        Returns:
        the distance between the two specified ids
      • distance

        public final double distance​(E e1,
                                     E e2)
        Returns the distance between the routing object of two entries.
        Parameters:
        e1 - First entry
        e2 - Second entry
        Returns:
        the distance between the two routing objects
      • createNewDirectoryEntry

        protected abstract E createNewDirectoryEntry​(N node,
                                                     DBID routingObjectID,
                                                     double parentDistance)
        Creates a new directory entry representing the specified node.
        Parameters:
        node - the node to be represented by the new entry
        routingObjectID - the id of the routing object of the node
        parentDistance - the distance from the routing object of the node to the routing object of the parent node
        Returns:
        the newly created directory entry
      • adjustTree

        private void adjustTree​(IndexTreePath<E> subtree)
        Adjusts the tree after insertion of some nodes.
        Parameters:
        subtree - the subtree to be adjusted
      • hasOverflow

        private boolean hasOverflow​(N node)
        Returns true if in the specified node an overflow has occurred, false otherwise.
        Parameters:
        node - the node to be tested for overflow
        Returns:
        true if in the specified node an overflow has occurred, false otherwise
      • createNewRoot

        private IndexTreePath<E> 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.
        Parameters:
        oldRoot - the old root of this RTree
        newNode - the new split node
        firstRoutingObjectID - the id of the routing objects of the first child node
        secondRoutingObjectID - the id of the routing objects of the second child node
        Returns:
        the path to the new root node that points to the two specified child nodes
      • getHeight

        public int getHeight()
        FIXME: expensive depth computation by following a path.
        Returns:
        depth
      • 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 AbstractMTreeNode<O,​N,​E>,​E extends MTreeEntry>
      • doExtraIntegrityChecks

        protected void doExtraIntegrityChecks()
        Perform additional integrity checks.