de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees
Class AbstractMkTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>
      de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,D,N,E>
          de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,N,E>
              de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,D,N,E>

Type Parameters:

O - the type of DatabaseObject to be stored in the metrical index

D - the type of Distance used in the metrical index

N - the type of MetricalNode used in the metrical index

E - the type of MetricalEntry used in the metrical index

Direct Known Subclasses:

AbstractMkTreeUnified, MkAppTree, MkCoPTree

public abstract class AbstractMkTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
extends AbstractMTree<O,D,N,E>

Abstract class for all M-Tree variants supporting processing of reverse k-nearest neighbor queries by using the k-nn distances of the entries, where k is less than or equal to the given parameter.

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

distanceFunction, distanceQuery, extraIntegrityChecks

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

AbstractMkTree(PageFile<N> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction)
Constructor.

Method Summary

abstract List<DistanceResultPair<D>>

reverseKNNQuery(DBID id, int k) Performs a reverse k-nearest neighbor query for the given object ID.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

batchNN, createEmptyRoot, createNewDirectoryEntry, distance, distance, doKNNQuery, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, insert, insertAll, toString

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeCapacities, initializeFromFile, isRoot, postDelete, preInsert, writeNode

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractMkTree

public AbstractMkTree(PageFile<N> pagefile,
                      DistanceQuery<O,D> distanceQuery,
                      DistanceFunction<O,D> distanceFunction)

Constructor.

Parameters:

pagefile - Page file

distanceQuery - Distance query

distanceFunction - Distance function

Method Detail

reverseKNNQuery

public abstract List<DistanceResultPair<D>> reverseKNNQuery(DBID 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.

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results