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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>
      extended by de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,D,N,E>
          extended by de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,D,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified<O,D,MkTabTreeNode<O,D>,MkTabEntry<D>>
                      extended by 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

Release 0.4.0 (2011-09-20_1324)