Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants
Class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndex<O,D,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,N,E>
Type Parameters:
O - the type of DatabaseObject to be stored in the metrical index
D - the type of Distance used in the metrical index
N - the type of MetricalNode used in the metrical index
E - the type of MetricalEntry used in the metrical index
All Implemented Interfaces:
Index<O>, Parameterizable
Direct Known Subclasses:
AbstractMkTree, MkAppTree, MkCoPTree, MTree

public abstract class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
extends MetricalIndex<O,D,N,E>

Abstract super class for all M-Tree variants.

Author:
Elke Achtert

Nested Class Summary
private  class AbstractMTree.SplitResult
          Encapsulates a split object and the newly created node.
 
Field Summary
static OptionID DISTANCE_FUNCTION_ID
          OptionID for DISTANCE_FUNCTION_PARAM
protected  ClassParameter<DistanceFunction<O,D>> DISTANCE_FUNCTION_PARAM
          Parameter to specify the distance function to determine the distance between database objects, must extend DistanceFunction.
private  DistanceFunction<O,D> distanceFunction
          Holds the instance of the distance function specified by DISTANCE_FUNCTION_PARAM.
protected static boolean 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
AbstractMTree()
          Provides a new abstract M-Tree and adds parameter DISTANCE_FUNCTION_PARAM to the option handler additionally to parameters of super class.
 
Method Summary
private  void adjustTree(TreeIndexPath<E> subtree)
          Adjusts the tree after insertion of some nodes.
protected  void batchNN(N node, List<Integer> ids, Map<Integer,KNNList<D>> knnLists)
          Performs a batch k-nearest neigbor query for a list of query objects.
private  TreeIndexPath<E> choosePath(Integer objectID, TreeIndexPath<E> subtree)
          Chooses the best path of the specified subtree for insertion of the given object.
protected  void createEmptyRoot(O object)
          Creates an empty root node and writes it to file.
protected abstract  E createNewDirectoryEntry(N node, Integer routingObjectID, D parentDistance)
          Creates a new directory entry representing the specified node.
protected abstract  E createNewLeafEntry(O object, D parentDistance)
          Creates a new leaf entry representing the specified data object.
private  TreeIndexPath<E> createNewRoot(N oldRoot, N newNode, Integer firstRoutingObjectID, Integer secondRoutingObjectID)
          Creates a new root node that points to the two specified child nodes and return the path to the new root.
 boolean delete(O o)
          Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.
protected  D distance(Integer id1, Integer id2)
          Returns the distance between the two specified ids.
protected  void doKNNQuery(Integer q, KNNList<D> knnList)
          Performs a k-nearest neighbor query for the given NumberVector with the given parameter k and the according distance function.
private  void doRangeQuery(Integer o_p, N node, Integer q, D r_q, List<DistanceResultPair<D>> result)
          Performs a range query on the specified subtree.
 DistanceFunction<O,D> getDistanceFunction()
          Returns the distance function of this metrical index.
protected  List<DistanceEntry<D,E>> getSortedEntries(N node, Integer q)
          Sorts the entries of the specified node according to their minimum distance to the specified object.
protected  List<DistanceEntry<D,E>> getSortedEntries(N node, Integer[] ids)
          Sorts the entries of the specified node according to their minimum distance to the specified objects.
private  List<DistanceEntry<D,E>> getSortedEntries(N node, List<Integer> ids)
          Sorts the entries of the specified node according to their minimum distance to the specified objects.
private  boolean hasOverflow(N node)
          Returns true if in the specified node an overflow has occurred, false otherwise.
protected  void insert(O object, boolean withPreInsert)
          Inserts the specified object into this M-Tree.
 List<DistanceResultPair<D>> kNNQuery(O object, int k)
          Performs a k-nearest neighbor query for the given object with the given parameter k and the according distance function.
protected  void postDelete(O o)
          Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.
 List<DistanceResultPair<D>> rangeQuery(O object, String epsilon)
          Performs a range query for the given object with the given epsilon range and the according distance function.
 void setDatabase(Database<O> database)
          Sets the database in the distance function of this index (if existing).
 List<String> setParameters(List<String> args)
          Calls TreeIndex#setParameters and instantiates distanceFunction according to the value of parameter DISTANCE_FUNCTION_PARAM.
private  AbstractMTree.SplitResult split(N node)
          Splits the specified node and returns the split result.
 String toString()
          Returns a string representation of this M-Tree by performing a breadth first enumeration on the tree and adding the string representation of the visited nodes and their entries to the result.
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndex
reverseKNNQuery
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
close, createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeCapacities, initializeFromFile, preInsert, 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.index.Index
insert, insert
 
Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription
 

Field Detail

extraIntegrityChecks

protected static final boolean extraIntegrityChecks
See Also:
Constant Field Values

DISTANCE_FUNCTION_ID

public static final OptionID DISTANCE_FUNCTION_ID
OptionID for DISTANCE_FUNCTION_PARAM


DISTANCE_FUNCTION_PARAM

protected final ClassParameter<DistanceFunction<O extends DatabaseObject,D extends Distance<D>>> DISTANCE_FUNCTION_PARAM
Parameter to specify the distance function to determine the distance between database objects, must extend DistanceFunction.

Key: -mtree.distancefunction

Default value: EuclideanDistanceFunction


distanceFunction

private DistanceFunction<O extends DatabaseObject,D extends Distance<D>> distanceFunction
Holds the instance of the distance function specified by DISTANCE_FUNCTION_PARAM.

Constructor Detail

AbstractMTree

public AbstractMTree()
Provides a new abstract M-Tree and adds parameter DISTANCE_FUNCTION_PARAM to the option handler additionally to parameters of super class.

Method Detail

delete

public final boolean delete(O o)
Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.

Parameters:
o - the object to be deleted
Returns:
true if this index did contain the object, false otherwise
Throws:
UnsupportedOperationException

postDelete

protected final void postDelete(O o)
Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.

Specified by:
postDelete in class TreeIndex<O extends DatabaseObject,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
Parameters:
o - the object to be deleted
Throws:
UnsupportedOperationException

rangeQuery

public final List<DistanceResultPair<D>> rangeQuery(O object,
                                                    String epsilon)
Description copied from class: MetricalIndex
Performs a range query for the given object with the given epsilon range and the according distance function. The query result is in ascending order to the distance to the query object.

Specified by:
rangeQuery in class MetricalIndex<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
Parameters:
object - the query object
epsilon - the string representation of the query range
Returns:
a List of the query results

kNNQuery

public final List<DistanceResultPair<D>> kNNQuery(O object,
                                                  int k)
Description copied from class: MetricalIndex
Performs a k-nearest neighbor query for the given object with the given parameter k and the according distance function. The query result is in ascending order to the distance to the query object.

Specified by:
kNNQuery in class MetricalIndex<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
Parameters:
object - the query object
k - the number of nearest neighbors to be returned
Returns:
a List of the query results

getDistanceFunction

public final DistanceFunction<O,D> getDistanceFunction()
Description copied from class: MetricalIndex
Returns the distance function of this metrical index.

Specified by:
getDistanceFunction in class MetricalIndex<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
Returns:
the distance function of this metrical index

toString

public String toString()
Returns a string representation of this M-Tree by performing a breadth first enumeration on the tree and adding the string representation of the visited nodes and their entries to the result.

Overrides:
toString in class Object
Returns:
a string representation of this M-Tree

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException
Calls TreeIndex#setParameters and instantiates distanceFunction according to the value of parameter DISTANCE_FUNCTION_PARAM. The remaining parameters are passed to the distanceFunction.

Specified by:
setParameters in interface Parameterizable
Overrides:
setParameters in class TreeIndex<O extends DatabaseObject,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
Parameters:
args - parameters to set the attributes accordingly to
Returns:
a list containing the unused parameters
Throws:
ParameterException - in case of wrong parameter-setting

setDatabase

public final void setDatabase(Database<O> database)
Description copied from interface: Index
Sets the database in the distance function of this index (if existing).

Parameters:
database - the database

insert

protected final void insert(O object,
                            boolean withPreInsert)
Inserts the specified object into this M-Tree.

Parameters:
object - the object to be inserted
withPreInsert - if this flag is true, the preInsert method will be called before inserting the object

createEmptyRoot

protected final void createEmptyRoot(O object)
Description copied from class: TreeIndex
Creates an empty root node and writes it to file.

Specified by:
createEmptyRoot in class TreeIndex<O extends DatabaseObject,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
Parameters:
object - an object that will be stored in the index

doKNNQuery

protected final void doKNNQuery(Integer q,
                                KNNList<D> knnList)
Performs a k-nearest neighbor query for the given NumberVector with the given parameter k and the according distance function. The query result is in ascending order to the distance to the query object.

Parameters:
q - the id of the query object
knnList - the query result list

choosePath

private TreeIndexPath<E> choosePath(Integer objectID,
                                    TreeIndexPath<E> subtree)
Chooses the best path of the specified subtree for insertion of the given object.

Parameters:
subtree - the subtree to be tested for insertion
objectID - the id of the object to be inserted
Returns:
the path of the appropriate subtree to insert the given object

batchNN

protected final void batchNN(N node,
                             List<Integer> ids,
                             Map<Integer,KNNList<D>> knnLists)
Performs a batch k-nearest neigbor query for a list of query objects.

Parameters:
node - the node reprsenting the subtree on which the query should be performed
ids - the ids of th query objects
knnLists - the knn lists of the query objcets

getSortedEntries

protected final List<DistanceEntry<D,E>> getSortedEntries(N node,
                                                          Integer q)
Sorts the entries of the specified node according to their minimum distance to the specified object.

Parameters:
node - the node
q - the id of the object
Returns:
a list of the sorted entries

getSortedEntries

protected final List<DistanceEntry<D,E>> getSortedEntries(N node,
                                                          Integer[] ids)
Sorts the entries of the specified node according to their minimum distance to the specified objects.

Parameters:
node - the node
ids - the ids of the objects
Returns:
a list of the sorted entries

distance

protected final D distance(Integer id1,
                           Integer id2)
Returns the distance between the two specified ids.

Parameters:
id1 - the first id
id2 - the second id
Returns:
the distance between the two specified ids

createNewLeafEntry

protected abstract E createNewLeafEntry(O object,
                                        D parentDistance)
Creates a new leaf entry representing the specified data object.

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 abstract E createNewDirectoryEntry(N node,
                                             Integer routingObjectID,
                                             D parentDistance)
Creates a new directory entry representing the specified node.

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

split

private AbstractMTree.SplitResult split(N node)
Splits the specified node and returns the split result.

Parameters:
node - the node to be splitted
Returns:
the split result

getSortedEntries

private List<DistanceEntry<D,E>> getSortedEntries(N node,
                                                  List<Integer> ids)
Sorts the entries of the specified node according to their minimum distance to the specified objects.

Parameters:
node - the node
ids - the ids of the objects
Returns:
a list of the sorted entries

doRangeQuery

private void doRangeQuery(Integer o_p,
                          N node,
                          Integer q,
                          D r_q,
                          List<DistanceResultPair<D>> result)
Performs a range query on the specified subtree. It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualifying objects.

Parameters:
o_p - the routing object of the specified node
node - the root of the subtree to be traversed
q - the id of the query object
r_q - the query range
result - the list holding the query results

adjustTree

private void adjustTree(TreeIndexPath<E> subtree)
Adjusts the tree after insertion of some nodes.

Parameters:
subtree - the subtree to be adjusted

hasOverflow

private boolean hasOverflow(N node)
Returns true if in the specified node an overflow has occurred, false otherwise.

Parameters:
node - the node to be tested for overflow
Returns:
true if in the specified node an overflow has occurred, false otherwise

createNewRoot

private TreeIndexPath<E> createNewRoot(N oldRoot,
                                       N newNode,
                                       Integer firstRoutingObjectID,
                                       Integer secondRoutingObjectID)
Creates a new root node that points to the two specified child nodes and return the path to the new root.

Parameters:
oldRoot - the old root of this RTree
newNode - the new split node
firstRoutingObjectID - the id of the routing objects of the first child node
secondRoutingObjectID - the id of the routing objects of the second child node
Returns:
the path to the new root node that points to the two specified child nodes

Release 0.2 (2009-07-06_1820)