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

All Implemented Interfaces:

Index<O>, Loggable, Parameterizable

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

DEFAULT_DISTANCE_FUNCTION, DISTANCE_FUNCTION_D, DISTANCE_FUNCTION_P

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

CACHE_SIZE_D, CACHE_SIZE_P, cacheSize, DEFAULT_CACHE_SIZE, DEFAULT_PAGE_SIZE, dirCapacity, dirMinimum, file, FILE_NAME_D, FILE_NAME_P, initialized, leafCapacity, leafMinimum, PAGE_SIZE_D, PAGE_SIZE_P, 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

Constructor Summary

MTree()
Provides a new M-Tree.

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 in the specified subtree.
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 void	preInsert(MTreeEntry<D> entry) Performs necessary operations before inserting the specified entry.

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

batchNN, choosePath, createEmptyRoot, delete, distance, doKNNQuery, getAttributeSettings, getDistanceFunction, getSortedEntries, getSortedEntries, initializeCapacities, insert, insert, insert, kNNQuery, postDelete, rangeQuery, reverseKNNQuery, setDatabase, setParameters, toString

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

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

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

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

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

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, 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, getParameters, getPossibleOptions, inlineDescription

Constructor Detail

MTree

public MTree()

Provides a new M-Tree.

Method Detail

preInsert

protected void preInsert(MTreeEntry<D> entry)

Performs necessary operations before inserting the specified 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

createNewLeafEntry

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

Description copied from class: AbstractMTree

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

the newly created leaf entry

See Also:

AbstractMTree.createNewLeafEntry(DatabaseObject, Distance)

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:

the newly created directory entry

See Also:

AbstractMTree.createNewDirectoryEntry(AbstractMTreeNode,Integer,Distance)

createRootEntry

protected MTreeEntry<D> createRootEntry()

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:

an entry representing the root node

createNewLeafNode

protected MTreeNode<O,D> createNewLeafNode(int capacity)

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 leaf node

createNewDirectoryNode

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

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 directory node