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

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          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,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

All Implemented Interfaces:

Index<O>, Parameterizable

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

Author:

Elke Achtert

Field Summary

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.utilities.optionhandling.AbstractParameterizable

optionHandler

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

debug, logger

Constructor Summary

MkTabTree()
Creates a new MkNNTabTree.

Method Summary

protected MkTabEntry<D>	createNewDirectoryEntry(MkTabTreeNode<O,D> node, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkTabTreeNode<O,D>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MkTabEntry<D>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object in the specified subtree.
protected MkTabTreeNode<O,D>	createNewLeafNode(int capacity) 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, Integer 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 void	initializeCapacities(O object, boolean verbose) 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(O object) Inserts the specified object into this index.
protected void	kNNdistanceAdjustment(MkTabEntry<D> entry, Map<Integer,KNNList<D>> knnLists) Performs a distance adjustment in the subtree of the specified root entry.
private List<D>	knnDistances(Integer objectID) Returns the knn distance of the object with the specified id.
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(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, setParameters

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, setDatabase, toString

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

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

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

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

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription

Constructor Detail

MkTabTree

public MkTabTree()

Creates a new MkNNTabTree.

Method Detail

preInsert

protected void preInsert(MkTabEntry<D> entry)

Description copied from class: TreeIndex

Performs necessary operations before inserting the specified entry.

Specified by:

preInsert in class TreeIndex<O extends DatabaseObject,MkTabTreeNode<O extends DatabaseObject,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(O object)

Description copied from interface: Index

Inserts the specified object into this index.

Parameters:

object - the vector to be inserted

Throws:

UnsupportedOperationException - since insertion of single objects is not supported

reverseKNNQuery

public List<DistanceResultPair<D>> reverseKNNQuery(O object,
                                                   int k)

Description copied from class: MetricalIndex

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 MetricalIndex<O extends DatabaseObject,D extends Distance<D>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<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

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,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

kNNdistanceAdjustment

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

Description copied from class: AbstractMkTree

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

Specified by:

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

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

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

Creates a new directory node with the specified capacity.

Specified by:

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

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

createNewLeafEntry

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

Creates a new leaf entry representing the specified data object in the specified subtree.

Specified by:

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

the newly created leaf entry

createNewDirectoryEntry

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

Creates a new directory entry representing the specified node.

Specified by:

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

Returns:

an entry representing the root node

doReverseKNNQuery

private void doReverseKNNQuery(int k,
                               Integer 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

knnDistances

private List<D> knnDistances(Integer objectID)

Returns the knn distance of the object with the specified id.

Parameters:

objectID - the id of the query object

Returns:

the knn distance of the object with the specified id

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