de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree
Class MTree<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,MTreeNode<O,D>,MTreeEntry<D>>
                  de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTree<O,D>

Type Parameters:

O - the type of DatabaseObject to be stored in the metrical index

D - the type of Distance used in the metrical index

All Implemented Interfaces:

Index<O>, Parameterizable

@Title(value="M-Tree")
@Description(value="Efficient Access Method for Similarity Search in Metric Spaces")
@Reference(authors="P. Ciaccia, M. Patella, P. Zezula",
           title="M-tree: An Efficient Access Method for Similarity Search in Metric Spaces",
           booktitle="VLDB\'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece",
           url="http://www.vldb.org/conf/1997/P426.PDF")
public class MTree<O extends DatabaseObject,D extends Distance<D>>
extends AbstractMTree<O,D,MTreeNode<O,D>,MTreeEntry<D>>

MTree is a metrical index structure based on the concepts of the M-Tree. Apart from organizing the objects it also provides several methods to search for certain object in the structure. Persistence is not yet ensured.

Author:

Elke Achtert

Field Summary

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

MTree(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

protected MTreeEntry<D>	createNewDirectoryEntry(MTreeNode<O,D> node, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MTreeNode<O,D>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MTreeEntry<D>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object.
protected MTreeNode<O,D>	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected MTreeEntry<D>	createRootEntry() Creates an entry representing the root node.
protected Class<MTreeNode<O,D>>	getNodeClass() Return the node base class.
protected void	initializeCapacities(O object, boolean verbose) Determines the maximum and minimum number of entries in a node.
void	insert(List<O> objects) Inserts the specified objects into this M-Tree sequentially since a bulk load method is not implemented so far.
void	insert(O object) Inserts the specified object into this M-Tree by calling AbstractMTree.insert(object, false).
protected void	preInsert(MTreeEntry<D> entry) Does nothing because no operations are necessary before inserting an entry.
List<DistanceResultPair<D>>	reverseKNNQuery(O object, int k) Throws an UnsupportedOperationException since reverse knn queries are not yet supported by an M-Tree.

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

Constructor Detail

MTree

public MTree(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

insert

public void insert(O object)

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

Parameters:

object - the object to be inserted

insert

public void insert(List<O> objects)

Inserts the specified objects into this M-Tree sequentially since a bulk load method is not implemented so far. Calls for each object AbstractMTree.insert(object, false).

Parameters:

objects - the objects to be inserted

preInsert

protected void preInsert(MTreeEntry<D> entry)

Does nothing because no operations are necessary before inserting an entry.

Specified by:

preInsert in class TreeIndex<O extends DatabaseObject,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Parameters:

entry - the entry to be inserted

reverseKNNQuery

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

Throws an UnsupportedOperationException since reverse knn queries are not yet supported by an M-Tree.

Specified by:

reverseKNNQuery in class MetricalIndex<O extends DatabaseObject,D extends Distance<D>,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<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

Throws:

UnsupportedOperationException - thrown since reverse kNN aren't implemented

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,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

createNewLeafEntry

protected MTreeEntry<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>,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<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 MTreeLeafEntry representing the specified data object

createNewDirectoryEntry

protected MTreeEntry<D> createNewDirectoryEntry(MTreeNode<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>,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<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 MTreeDirectoryEntry representing the specified node

createRootEntry

protected MTreeEntry<D> createRootEntry()

Description copied from class: TreeIndex

Creates an entry representing the root node.

Specified by:

createRootEntry in class TreeIndex<O extends DatabaseObject,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Returns:

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

createNewLeafNode

protected MTreeNode<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,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new MTreeNode which is a leaf node

createNewDirectoryNode

protected MTreeNode<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,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new MTreeNode which is a directory node

getNodeClass

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

Return the node base class.

Specified by:

getNodeClass in class TreeIndex<O extends DatabaseObject,MTreeNode<O extends DatabaseObject,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Returns:

node base class