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

Class MkMaxTree<O>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,N,E>

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

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

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax.MkMaxTree<O>

Type Parameters:

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

All Implemented Interfaces:

Index, Result

Direct Known Subclasses:

MkMaxTreeIndex

public abstract class MkMaxTree<O>
extends AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>

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

Since:

0.2

Author:

Elke Achtert

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 static Logging	LOG The logger for this class.

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

knnq

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
MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O>> pagefile, MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry> settings) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected MkMaxEntry	createNewDirectoryEntry(MkMaxTreeNode<O> node, DBID routingObjectID, double parentDistance) Creates a new directory entry representing the specified node.
protected MkMaxTreeNode<O>	createNewDirectoryNode() Creates a new directory node with the specified capacity.
protected MkMaxTreeNode<O>	createNewLeafNode() Creates a new leaf node with the specified capacity.
protected MkMaxEntry	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O> node, MkMaxEntry node_entry, ModifiableDoubleDBIDList result) Performs a reverse k-nearest neighbor query in the specified subtree for the given query object with k = AbstractMkTreeUnified.getKmax().
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	initializeCapacities(MkMaxEntry exampleLeaf) Determines the maximum and minimum number of entries in a node.
protected void	kNNdistanceAdjustment(MkMaxEntry entry, Map<DBID,KNNList> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
protected void	preInsert(MkMaxEntry entry) Adapts the knn distances before insertion of the specified entry.
private void	preInsert(MkMaxEntry q, MkMaxEntry nodeEntry, KNNHeap knns_q) Adapts the knn distances before insertion of entry q.
DoubleDBIDList	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.mktrees.AbstractMkTreeUnified

createHeader, getKmax, insertAll

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

batchNN, distance

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

createEmptyRoot, distance, getDistanceFunction, getHeight, getLeaves, getSortedEntries, insert, logStatistics, toString

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

deleteNode, getFile, getNode, getNode, 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

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

getLongName, getShortName

Field Detail

LOG

private static final Logging LOG

The logger for this class.

Constructor Detail

MkMaxTree

public MkMaxTree(Relation<O> relation,
         PageFile<MkMaxTreeNode<O>> pagefile,
         MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry> settings)

Constructor.

Parameters:

relation - Relation to index

pagefile - Page file

settings - Tree settings

Method Detail

reverseKNNQuery

public DoubleDBIDList reverseKNNQuery(DBIDRef 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.getKmax(). Then these candidates are refined in a second step.

Specified by:

reverseKNNQuery in class AbstractMkTree<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

preInsert

protected void preInsert(MkMaxEntry entry)

Adapts the knn distances before insertion of the specified entry.

Overrides:

preInsert in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>

Parameters:

entry - the entry to be inserted

kNNdistanceAdjustment

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

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

Specified by:

kNNdistanceAdjustment in class AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>

Parameters:

entry - the root entry of the current subtree

knnLists - a map of knn lists for each leaf entry

doReverseKNNQuery

private void doReverseKNNQuery(DBIDRef q,
                     MkMaxTreeNode<O> node,
                     MkMaxEntry node_entry,
                     ModifiableDoubleDBIDList result)

Performs a reverse k-nearest neighbor query in the specified subtree for the given query object with k = AbstractMkTreeUnified.getKmax(). It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualifying 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 q,
             MkMaxEntry nodeEntry,
             KNNHeap 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 the current subtree

knns_q - the knns of q

initializeCapacities

protected void initializeCapacities(MkMaxEntry 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>,MkMaxEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

createNewLeafNode

protected MkMaxTreeNode<O> createNewLeafNode()

Description copied from class: IndexTree

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>

Returns:

a new MkMaxTreeNode which is a leaf node

createNewDirectoryNode

protected MkMaxTreeNode<O> createNewDirectoryNode()

Description copied from class: IndexTree

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>

Returns:

a new MkMaxTreeNode which is a directory node

createNewDirectoryEntry

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

Description copied from class: AbstractMTree

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>

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 createRootEntry()

Description copied from class: IndexTree

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>

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

Returns:

the static logger