Class MkAppTree<O>

  • Type Parameters:
    O - the type of DatabaseObject to be stored in the metrical index
    All Implemented Interfaces:
    Index
    Direct Known Subclasses:
    MkAppTreeIndex

    public abstract class MkAppTree<O>
    extends AbstractMkTree<O,​MkAppTreeNode<O>,​MkAppEntry,​MkAppTreeSettings<O>>
    MkAppTree 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.
    Since:
    0.1
    Author:
    Elke Achtert
    • Field Detail

      • LOG

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

      • insert

        public void insert​(MkAppEntry id,
                           boolean withPreInsert)
        Description copied from class: AbstractMTree
        Inserts the specified object into this M-Tree.
        Overrides:
        insert in class AbstractMTree<O,​MkAppTreeNode<O>,​MkAppEntry,​MkAppTreeSettings<O>>
        Parameters:
        id - 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 this operation is not supported
      • preInsert

        protected void preInsert​(MkAppEntry entry)
        Description copied from class: IndexTree
        Performs necessary operations before inserting the specified entry.
        Overrides:
        preInsert in class IndexTree<MkAppTreeNode<O>,​MkAppEntry>
        Parameters:
        entry - the entry to be inserted
        Throws:
        java.lang.UnsupportedOperationException - since this operation is not supported
      • reverseKNNQuery

        public DoubleDBIDList reverseKNNQuery​(DBIDRef id,
                                              int k)
        Performs a reverse k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.
        Specified by:
        reverseKNNQuery in class AbstractMkTree<O,​MkAppTreeNode<O>,​MkAppEntry,​MkAppTreeSettings<O>>
        Parameters:
        id - the query object id
        k - the number of nearest neighbors to be returned
        Returns:
        a List of the query results
      • getK_max

        public int getK_max()
        Returns the value of the k_max parameter.
        Returns:
        the value of the k_max parameter
      • getMeanKNNList

        private double[] getMeanKNNList​(DBIDs ids,
                                        java.util.Map<DBID,​KNNList> knnLists)
      • adjustApproximatedKNNDistances

        private void adjustApproximatedKNNDistances​(MkAppEntry entry,
                                                    java.util.Map<DBID,​KNNList> knnLists)
        Adjusts the knn distance in the subtree of the specified root entry.
        Parameters:
        entry - the root entry of the current subtree
        knnLists - a map of knn lists for each leaf entry
      • leafEntryIDs

        private void leafEntryIDs​(MkAppTreeNode<O> node,
                                  ModifiableDBIDs result)
        Determines the ids of the leaf entries stored in the specified subtree.
        Parameters:
        node - the root of the subtree
        result - the result list containing the ids of the leaf entries stored in the specified subtree
      • approximateKnnDistances

        private PolynomialApproximation approximateKnnDistances​(double[] knnDistances)
        Computes the polynomial approximation of the specified knn-distances.
        Parameters:
        knnDistances - the knn-distances of the leaf entry
        Returns:
        the polynomial approximation of the specified knn-distances.
      • createNewDirectoryEntry

        protected MkAppEntry createNewDirectoryEntry​(MkAppTreeNode<O> node,
                                                     DBID routingObjectID,
                                                     double parentDistance)
        Creates a new directory entry representing the specified node.
        Specified by:
        createNewDirectoryEntry in class AbstractMTree<O,​MkAppTreeNode<O>,​MkAppEntry,​MkAppTreeSettings<O>>
        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