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

Modifier and Type	Field and Description
protected KNNQuery<O,D>	knnq Internal class for performing knn queries

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

distanceFunction, distanceQuery, EXTRA_INTEGRITY_CHECKS

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and Description
protected Map<DBID,KNNResult<D>>	batchNN(N node, DBIDs ids, int kmax) Deprecated. Change to use by-object NN lookups instead.
abstract DistanceDBIDResult<D>	reverseKNNQuery(DBIDRef 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

createEmptyRoot, createNewDirectoryEntry, distance, 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

Field Detail

knnq

protected KNNQuery<O,D extends Distance<D>> knnq

Internal class for performing knn queries

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 DistanceDBIDResult<D> 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.

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

batchNN

@Deprecated
protected final Map<DBID,KNNResult<D>> batchNN(N node,
                                        DBIDs ids,
                                        int kmax)

Deprecated. Change to use by-object NN lookups instead.

Performs a batch k-nearest neighbor query for a list of query objects.

Parameters:

node - the node representing the subtree on which the query should be performed

ids - the ids of the query objects

kmax - Maximum k value