de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree

Class MTree<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,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

Direct Known Subclasses:

MTreeIndex

@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,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.

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.AbstractMTree

distanceFunction, distanceQuery, EXTRA_INTEGRITY_CHECKS

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
MTree(PageFile<MTreeNode<O,D>> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected MTreeEntry<D>	createNewDirectoryEntry(MTreeNode<O,D> node, DBID routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MTreeNode<O,D>	createNewDirectoryNode() Creates a new directory node with the specified capacity.
protected MTreeNode<O,D>	createNewLeafNode() Creates a new leaf node with the specified capacity.
protected MTreeEntry<D>	createRootEntry() Creates an entry representing the root node.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	initializeCapacities(MTreeEntry<D> exampleLeaf) Determines the maximum and minimum number of entries in a node.
protected void	preInsert(MTreeEntry<D> entry) Does nothing because no operations are necessary before inserting an entry.

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

createEmptyRoot, distance, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, insert, insertAll, toString

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

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

LOG

private static final Logging LOG

The logger for this class.

Constructor Detail

MTree

public MTree(PageFile<MTreeNode<O,D>> pagefile,
     DistanceQuery<O,D> distanceQuery,
     DistanceFunction<O,D> distanceFunction)

Constructor.

Parameters:

pagefile - Page file

distanceQuery - Distance query

distanceFunction - Distance function

Method Detail

preInsert

protected void preInsert(MTreeEntry<D> entry)

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

Overrides:

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

Parameters:

entry - the entry to be inserted

initializeCapacities

protected void initializeCapacities(MTreeEntry<D> exampleLeaf)

Description copied from class: IndexTree

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

Specified by:

initializeCapacities in class IndexTree<MTreeNode<O,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Parameters:

exampleLeaf - an object that will be stored in the index

createNewDirectoryEntry

protected MTreeEntry<D> createNewDirectoryEntry(MTreeNode<O,D> node,
                                    DBID routingObjectID,
                                    D parentDistance)

Description copied from class: AbstractMTree

Creates a new directory entry representing the specified node.

Specified by:

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

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<MTreeNode<O,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()

Description copied from class: IndexTree

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<MTreeNode<O,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Returns:

a new MTreeNode which is a leaf node

createNewDirectoryNode

protected MTreeNode<O,D> createNewDirectoryNode()

Description copied from class: IndexTree

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<MTreeNode<O,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Returns:

a new MTreeNode which is a directory node

getLogger

protected Logging getLogger()

Description copied from class: IndexTree

Get the (STATIC) logger for this class.

Specified by:

getLogger in class IndexTree<MTreeNode<O,D extends Distance<D>>,MTreeEntry<D extends Distance<D>>>

Returns:

the static logger