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
  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,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 ObjectParameter<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 Debugging flag: do extra integrity checks

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

AbstractMTree(Parameterization config)
Constructor, adhering to Parameterizable

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 FeatureVector 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, D epsilon) Performs a range query for the given object with the given epsilon range and the according distance function.
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).
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, getFileName, getLogicalPageAccess, getNode, getNode, getNodeClass, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeCapacities, initializeFromFile, preInsert, 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

Methods inherited from interface de.lmu.ifi.dbs.elki.index.Index

insert, insert

Field Detail

extraIntegrityChecks

protected static final boolean extraIntegrityChecks

Debugging flag: do extra integrity checks

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 ObjectParameter<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(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

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 - thrown, since deletions aren't implemented yet.

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

rangeQuery

public final List<DistanceResultPair<D>> rangeQuery(O object,
                                                    D 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

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 FeatureVector 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 split

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