Class MkTabTree<O>

  • Type Parameters:
    O - Object type
    All Implemented Interfaces:
    Index
    Direct Known Subclasses:
    MkTabTreeIndex

    public abstract class MkTabTree<O>
    extends AbstractMkTreeUnified<O,​MkTabTreeNode<O>,​MkTabEntry,​MkTreeSettings<O,​MkTabTreeNode<O>,​MkTabEntry>>
    MkTabTree is a metrical index structure based on the concepts of the M-Tree supporting efficient processing of reverse k nearest neighbor queries for parameter k < kmax. All knn distances for k <= kmax are stored in each entry of a node.
    Since:
    0.1
    Author:
    Elke Achtert
    • Field Detail

      • LOG

        private static final Logging LOG
        The logger for this class.
    • Method Detail

      • preInsert

        protected void preInsert​(MkTabEntry entry)
        Description copied from class: IndexTree
        Performs necessary operations before inserting the specified entry.
        Overrides:
        preInsert in class IndexTree<MkTabTreeNode<O>,​MkTabEntry>
        Parameters:
        entry - the entry to be inserted
        Throws:
        java.lang.UnsupportedOperationException - since insertion of single objects is not supported
      • insert

        public void insert​(MkTabEntry entry,
                           boolean withPreInsert)
        Description copied from class: AbstractMTree
        Inserts the specified object into this M-Tree.
        Overrides:
        insert in class AbstractMTree<O,​MkTabTreeNode<O>,​MkTabEntry,​MkTreeSettings<O,​MkTabTreeNode<O>,​MkTabEntry>>
        Parameters:
        entry - the entry to be inserted
        withPreInsert - if this flag is true, the preInsert method will be called before inserting the object
        Throws:
        java.lang.UnsupportedOperationException - since insertion of single objects is not supported
      • doReverseKNNQuery

        private void doReverseKNNQuery​(int k,
                                       DBIDRef q,
                                       MkTabEntry node_entry,
                                       MkTabTreeNode<O> node,
                                       ModifiableDoubleDBIDList result)
        Performs a k-nearest neighbor query in the specified subtree for the given query object and the given parameter k. It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualifying objects.
        Parameters:
        k - the parameter k of the knn-query
        q - the id of the query object
        node_entry - the entry representing the node
        node - the root of the subtree
        result - the list holding the query result
      • max

        private double[] max​(double[] distances1,
                             double[] distances2)
        Returns an array that holds the maximum values of the both specified arrays in each index.
        Parameters:
        distances1 - the first array
        distances2 - the second array
        Returns:
        an array that holds the maximum values of the both specified arrays in each index
      • initKnnDistanceList

        private double[] initKnnDistanceList()
        Returns a knn distance list with all distances set to null distance.
        Returns:
        a knn distance list with all distances set to null distance