de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax
Class MkMaxTree<O extends DatabaseObject,D extends Distance<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
          de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndex<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,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

All Implemented Interfaces:

Index<O>, Parameterizable

public class MkMaxTree<O extends DatabaseObject,D extends Distance<D>>
extends AbstractMkTree<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.

Author:

Elke Achtert

Field Summary

private QueryStatistic

rkNNStatistics Provides some statistics about performed reverse knn-queries.

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

k_max, K_MAX_ID, K_MAX_PARAM

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

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM, extraIntegrityChecks

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

CACHE_SIZE_ID, cacheSize, dirCapacity, dirMinimum, file, FILE_ID, initialized, leafCapacity, leafMinimum, PAGE_SIZE_ID, pageSize

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

MkMaxTree(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

void	clearRkNNStatistics() Clears the values of the statistic for performed rknn queries
protected MkMaxEntry<D>	createNewDirectoryEntry(MkMaxTreeNode<O,D> node, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkMaxTreeNode<O,D>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MkMaxEntry<D>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object.
protected MkMaxTreeNode<O,D>	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected MkMaxEntry<D>	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNNQuery(Integer 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 = AbstractMkTree.k_max.
protected Class<MkMaxTreeNode<O,D>>	getNodeClass() Return the node base class.
QueryStatistic	getRkNNStatistics() Returns the statistic for performed rknn queries.
protected void	initializeCapacities(O object, boolean verbose) Determines the maximum and minimum number of entries in a node.
void	insert(O object) Inserts the specified object into this MkMax-Tree by calling AbstractMTree.insert(object, true).
protected void	kNNdistanceAdjustment(MkMaxEntry<D> entry, Map<Integer,KNNList<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, KNNList<D> knns_q) Adapts the knn distances before insertion of entry q.
List<DistanceResultPair<D>>	reverseKNNQuery(O object, 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.AbstractMkTree

createHeader, insert

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

batchNN, createEmptyRoot, delete, distance, doKNNQuery, getDistanceFunction, getSortedEntries, getSortedEntries, insert, kNNQuery, postDelete, rangeQuery, rangeQuery, setDatabase, toString

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

close, getFileName, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeFromFile, resetPageAccess

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, progress, verbose, warning

Methods inherited from class java.lang.Object

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

Field Detail

rkNNStatistics

private QueryStatistic rkNNStatistics

Provides some statistics about performed reverse knn-queries.

Constructor Detail

MkMaxTree

public MkMaxTree(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

insert

public void insert(O object)

Inserts the specified object into this MkMax-Tree by calling AbstractMTree.insert(object, true).

Parameters:

object - the object to be inserted

reverseKNNQuery

public List<DistanceResultPair<D>> reverseKNNQuery(O object,
                                                   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 = AbstractMkTree.k_max. Then these candidates are refined in a second step.

Specified by:

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

Parameters:

object - the query object

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.

Specified by:

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

Parameters:

entry - the entry to be inserted

kNNdistanceAdjustment

protected void kNNdistanceAdjustment(MkMaxEntry<D> entry,
                                     Map<Integer,KNNList<D>> knnLists)

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

Specified by:

kNNdistanceAdjustment in class AbstractMkTree<O extends DatabaseObject,D extends Distance<D>,MkMaxTreeNode<O extends DatabaseObject,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(Integer 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 = AbstractMkTree.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,
                       KNNList<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(O object,
                                    boolean verbose)

Description copied from class: TreeIndex

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

Specified by:

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

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

createNewLeafNode

protected MkMaxTreeNode<O,D> createNewLeafNode(int capacity)

Description copied from class: TreeIndex

Creates a new leaf node with the specified capacity.

Specified by:

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

Parameters:

capacity - the capacity of the new node

Returns:

a new MkMaxTreeNode which is a leaf node

createNewDirectoryNode

protected MkMaxTreeNode<O,D> createNewDirectoryNode(int capacity)

Description copied from class: TreeIndex

Creates a new directory node with the specified capacity.

Specified by:

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

Parameters:

capacity - the capacity of the new node

Returns:

a new MkMaxTreeNode which is a directory node

createNewLeafEntry

protected MkMaxEntry<D> createNewLeafEntry(O object,
                                           D parentDistance)

Description copied from class: AbstractMTree

Creates a new leaf entry representing the specified data object.

Specified by:

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

Parameters:

object - the data object to be represented by the new entry

parentDistance - the distance from the object to the routing object of the parent node

Returns:

a new MkMaxLeafEntry representing the specified data object

createNewDirectoryEntry

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

Description copied from class: AbstractMTree

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,MkMaxTreeNode<O extends DatabaseObject,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: TreeIndex

Creates an entry representing the root node.

Specified by:

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

Returns:

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

getNodeClass

protected Class<MkMaxTreeNode<O,D>> getNodeClass()

Return the node base class.

Specified by:

getNodeClass in class TreeIndex<O extends DatabaseObject,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

node base class