de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax
Class MkMaxTree<O,D extends Distance<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>
                  de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified<O,D,MkMaxTreeNode<O,D>,MkMaxEntry<D>>
                      de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax.MkMaxTree<O,D>

Type Parameters:

O - the type of DatabaseObject to be stored in the MkMaxTree

D - the type of Distance used in the MkMaxTree

Direct Known Subclasses:

MkMaxTreeIndex

public class MkMaxTree<O,D extends Distance<D>>
extends AbstractMkTreeUnified<O,D,MkMaxTreeNode<O,D>,MkMaxEntry<D>>

MkMaxTree 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 <= k_max. The k-nearest neigbor distance for k = k_max is stored in each entry of a node.

Field Summary

private static Logging	logger The logger for this class.
private QueryStatistic	rkNNStatistics Provides some statistics about performed reverse knn-queries.

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

MkMaxTree(PageFile<MkMaxTreeNode<O,D>> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction, int k_max)
Constructor.

Method Summary

void	clearRkNNStatistics() Clears the values of the statistic for performed rknn queries
protected MkMaxEntry<D>	createNewDirectoryEntry(MkMaxTreeNode<O,D> node, DBID routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkMaxTreeNode<O,D>	createNewDirectoryNode() Creates a new directory node with the specified capacity.
protected MkMaxTreeNode<O,D>	createNewLeafNode() Creates a new leaf node with the specified capacity.
protected MkMaxEntry<D>	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNNQuery(DBID q, MkMaxTreeNode<O,D> node, MkMaxEntry<D> node_entry, List<DistanceResultPair<D>> result) Performs a reverse k-nearest neighbor query in the specified subtree for the given query object with k = AbstractMkTreeUnified.k_max.
protected Logging	getLogger() Get the (STATIC) logger for this class.
QueryStatistic	getRkNNStatistics() Returns the statistic for performed rknn queries.
protected void	initializeCapacities(MkMaxEntry<D> exampleLeaf) Determines the maximum and minimum number of entries in a node.
protected void	kNNdistanceAdjustment(MkMaxEntry<D> entry, Map<DBID,KNNHeap<D>> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
protected void	preInsert(MkMaxEntry<D> entry) Adapts the knn distances before insertion of the specified entry.
private void	preInsert(MkMaxEntry<D> q, MkMaxEntry<D> nodeEntry, KNNHeap<D> knns_q) Adapts the knn distances before insertion of entry q.
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.mktrees.AbstractMkTreeUnified

createHeader, getKmax, insertAll

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

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

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

deleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode

Methods inherited from class java.lang.Object

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

Field Detail

logger

private static final Logging logger

The logger for this class.

rkNNStatistics

private QueryStatistic rkNNStatistics

Provides some statistics about performed reverse knn-queries.

Constructor Detail

MkMaxTree

public MkMaxTree(PageFile<MkMaxTreeNode<O,D>> pagefile,
                 DistanceQuery<O,D> distanceQuery,
                 DistanceFunction<O,D> distanceFunction,
                 int k_max)

Constructor.

Parameters:

pagefile - Page file

distanceQuery - Distance query

distanceFunction - Distance function

k_max - Maximum value for k

Method Detail

reverseKNNQuery

public List<DistanceResultPair<D>> reverseKNNQuery(DBID id,
                                                   int k)

Performs a reverse k-nearest neighbor query for the given object ID. In the first step the candidates are chosen by performing a reverse k-nearest neighbor query with k = AbstractMkTreeUnified.k_max. Then these candidates are refined in a second step.

Specified by:

reverseKNNQuery in class AbstractMkTree<O,D extends Distance<D>,MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

getRkNNStatistics

public QueryStatistic getRkNNStatistics()

Returns the statistic for performed rknn queries.

Returns:

the statistic for performed rknn queries

clearRkNNStatistics

public void clearRkNNStatistics()

Clears the values of the statistic for performed rknn queries

preInsert

protected void preInsert(MkMaxEntry<D> entry)

Adapts the knn distances before insertion of the specified entry.

Overrides:

preInsert in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

entry - the entry to be inserted

kNNdistanceAdjustment

protected void kNNdistanceAdjustment(MkMaxEntry<D> entry,
                                     Map<DBID,KNNHeap<D>> knnLists)

Adjusts the knn distance in the subtree of the specified root entry.

Specified by:

kNNdistanceAdjustment in class AbstractMkTreeUnified<O,D extends Distance<D>,MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

entry - the root entry of the current subtree

knnLists - a map of knn lists for each leaf entry

doReverseKNNQuery

private void doReverseKNNQuery(DBID q,
                               MkMaxTreeNode<O,D> node,
                               MkMaxEntry<D> node_entry,
                               List<DistanceResultPair<D>> result)

Performs a reverse k-nearest neighbor query in the specified subtree for the given query object with k = AbstractMkTreeUnified.k_max. It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualififying objects.

Parameters:

q - the id of the query object

node - the node of the subtree on which the query is performed

node_entry - the entry representing the node

result - the list for the query result

preInsert

private void preInsert(MkMaxEntry<D> q,
                       MkMaxEntry<D> nodeEntry,
                       KNNHeap<D> knns_q)

Adapts the knn distances before insertion of entry q.

Parameters:

q - the entry to be inserted

nodeEntry - the entry representing the root of thge current subtree

knns_q - the knns of q

initializeCapacities

protected void initializeCapacities(MkMaxEntry<D> exampleLeaf)

Description copied from class: IndexTree

Determines the maximum and minimum number of entries in a node.

Specified by:

initializeCapacities in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

exampleLeaf - an object that will be stored in the index

createNewLeafNode

protected MkMaxTreeNode<O,D> createNewLeafNode()

Description copied from class: IndexTree

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

a new MkMaxTreeNode which is a leaf node

createNewDirectoryNode

protected MkMaxTreeNode<O,D> createNewDirectoryNode()

Description copied from class: IndexTree

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

a new MkMaxTreeNode which is a directory node

createNewDirectoryEntry

protected MkMaxEntry<D> createNewDirectoryEntry(MkMaxTreeNode<O,D> node,
                                                DBID routingObjectID,
                                                D parentDistance)

Description copied from class: AbstractMTree

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O,D extends Distance<D>,MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

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:

a new MkMaxDirectoryEntry representing the specified node

createRootEntry

protected MkMaxEntry<D> createRootEntry()

Description copied from class: IndexTree

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

a new MkMaxDirectoryEntry by calling new MkMaxDirectoryEntry(null, null, 0, null)

getLogger

protected Logging getLogger()

Description copied from class: IndexTree

Get the (STATIC) logger for this class.

Specified by:

getLogger in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

the static logger