de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab
Class MkTabTree<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,MkTabTreeNode<O,D>,MkTabEntry<D>>
                      de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab.MkTabTree<O,D>

Type Parameters:

O - Object type

D - Distance type

Direct Known Subclasses:

MkTabTreeIndex

public class MkTabTree<O,D extends Distance<D>>
extends AbstractMkTreeUnified<O,D,MkTabTreeNode<O,D>,MkTabEntry<D>>

MkTabTree 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 < kmax. All knn distances for k <= kmax are stored in each entry of a node.

Field Summary

private static Logging

logger The logger for this class.

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

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

Method Summary

protected MkTabEntry<D>	createNewDirectoryEntry(MkTabTreeNode<O,D> node, DBID routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkTabTreeNode<O,D>	createNewDirectoryNode() Creates a new directory node with the specified capacity.
protected MkTabTreeNode<O,D>	createNewLeafNode() Creates a new leaf node with the specified capacity.
protected MkTabEntry<D>	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNNQuery(int k, DBID q, MkTabEntry<D> node_entry, MkTabTreeNode<O,D> node, List<DistanceResultPair<D>> result) Performs a k-nearest neighbor query in the specified subtree for the given query object and the given parameter k.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	initializeCapacities(MkTabEntry<D> exampleLeaf) Determines the maximum and minimum number of entries in a node.
private List<D>	initKnnDistanceList() Returns a knn distance list with all distances set to null distance.
void	insert(MkTabEntry<D> entry, boolean withPreInsert) Inserts the specified object into this M-Tree.
protected void	kNNdistanceAdjustment(MkTabEntry<D> entry, Map<DBID,KNNHeap<D>> knnLists) Performs a distance adjustment in the subtree of the specified root entry.
private List<D>	max(List<D> distances1, List<D> distances2) Returns an array that holds the maximum values of the both specified arrays in each index.
protected void	preInsert(MkTabEntry<D> entry) Performs necessary operations before inserting the specified entry.
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, 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.

Constructor Detail

MkTabTree

public MkTabTree(PageFile<MkTabTreeNode<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

preInsert

protected void preInsert(MkTabEntry<D> entry)

Description copied from class: IndexTree

Performs necessary operations before inserting the specified entry.

Overrides:

preInsert in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

entry - the entry to be inserted

Throws:

UnsupportedOperationException - since insertion of single objects is not supported

insert

public void insert(MkTabEntry<D> entry,
                   boolean withPreInsert)

Description copied from class: AbstractMTree

Inserts the specified object into this M-Tree.

Overrides:

insert in class AbstractMTree<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

entry - the entry to be inserted

withPreInsert - if this flag is true, the preInsert method will be called before inserting the object

Throws:

UnsupportedOperationException - since insertion of single objects is not supported

reverseKNNQuery

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

Description copied from class: AbstractMkTree

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.

Specified by:

reverseKNNQuery in class AbstractMkTree<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<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

initializeCapacities

protected void initializeCapacities(MkTabEntry<D> exampleLeaf)

Description copied from class: IndexTree

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

Specified by:

initializeCapacities in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

exampleLeaf - an object that will be stored in the index

kNNdistanceAdjustment

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

Description copied from class: AbstractMkTreeUnified

Performs a distance adjustment in the subtree of the specified root entry.

Specified by:

kNNdistanceAdjustment in class AbstractMkTreeUnified<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

entry - the root entry of the current subtree

knnLists - a map of knn lists for each leaf entry

createNewLeafNode

protected MkTabTreeNode<O,D> createNewLeafNode()

Description copied from class: IndexTree

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Returns:

a new leaf node

createNewDirectoryNode

protected MkTabTreeNode<O,D> createNewDirectoryNode()

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Returns:

a new directory node

createNewDirectoryEntry

protected MkTabEntry<D> createNewDirectoryEntry(MkTabTreeNode<O,D> node,
                                                DBID routingObjectID,
                                                D parentDistance)

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<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:

the newly created directory entry

createRootEntry

protected MkTabEntry<D> createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Returns:

an entry representing the root node

doReverseKNNQuery

private void doReverseKNNQuery(int k,
                               DBID q,
                               MkTabEntry<D> node_entry,
                               MkTabTreeNode<O,D> node,
                               List<DistanceResultPair<D>> result)

Performs a k-nearest neighbor query in the specified subtree for the given query object and the given parameter k. It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualifying objects.

Parameters:

k - the parameter k of the knn-query

q - the id of the query object

node_entry - the entry representing the node

node - the root of the subtree

result - the list holding the query result

max

private List<D> max(List<D> distances1,
                    List<D> distances2)

Returns an array that holds the maximum values of the both specified arrays in each index.

Parameters:

distances1 - the first array

distances2 - the second array

Returns:

an array that holds the maximum values of the both specified arrays in each index

initKnnDistanceList

private List<D> initKnnDistanceList()

Returns a knn distance list with all distances set to null distance.

Returns:

a knn distance list with all distances set to null distance

getLogger

protected Logging getLogger()

Description copied from class: IndexTree

Get the (STATIC) logger for this class.

Specified by:

getLogger in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Returns:

the static logger