de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees

Class AbstractMkTree<O,D extends NumberDistance<D,?>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,D,N,E>>

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,S>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,D,N,E,S>

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

S - the type of Settings kept.

Direct Known Subclasses:

AbstractMkTreeUnified, MkAppTree, MkCoPTree

public abstract class AbstractMkTree<O,D extends NumberDistance<D,?>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,D,N,E>>
extends AbstractMTree<O,D,N,E,S>

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.

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

AbstractMTree.Statistics

Field Summary

Fields

Modifier and Type	Field and Description
private DistanceQuery<O,D>	distanceQuery Distance query to use.
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

EXTRA_INTEGRITY_CHECKS, settings, statistics

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
AbstractMkTree(Relation<O> relation, PageFile<N> pagefile, S settings) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected Map<DBID,KNNList<D>>	batchNN(N node, DBIDs ids, int kmax) Deprecated. Change to use by-object NN lookups instead.
D	distance(DBIDRef id1, DBIDRef id2) Returns the distance between the two specified ids.
abstract DistanceDBIDList<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, getHeight, getLeaves, getSortedEntries, insert, insertAll, logStatistics, toString

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

createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, 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 NumberDistance<D,?>> knnq

Internal class for performing knn queries

distanceQuery

private DistanceQuery<O,D extends NumberDistance<D,?>> distanceQuery

Distance query to use.

Constructor Detail

AbstractMkTree

public AbstractMkTree(Relation<O> relation,
              PageFile<N> pagefile,
              S settings)

Constructor.

Parameters:

relation - Relation to index

pagefile - Page file

settings - Settings class

Method Detail

distance

public D distance(DBIDRef id1,
         DBIDRef id2)

Description copied from class: AbstractMTree

Returns the distance between the two specified ids.

Specified by:

distance in class AbstractMTree<O,D extends NumberDistance<D,?>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,D,N,E>>

Parameters:

id1 - the first id

id2 - the second id

Returns:

the distance between the two specified ids

reverseKNNQuery

public abstract DistanceDBIDList<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,KNNList<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