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.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,N,E>

All Implemented Interfaces:

Index<O>, Loggable, Parameterizable

Direct Known Subclasses:

MkAppTree, MkCoPTree, MkMaxTree, MkTabTree, 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 String	DEFAULT_DISTANCE_FUNCTION The default distance function.
static String	DISTANCE_FUNCTION_D Description for parameter distance function.
static String	DISTANCE_FUNCTION_P Parameter for distance function.
private DistanceFunction<O,D>	distanceFunction The distance function.

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

AbstractMTree()
Empty constructor.

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 knn query.
protected 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 in the specified subtree.
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) Deletes the specified obect from this index.
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<QueryResult<D>> result) Performs a range query.
List<AttributeSettings>	getAttributeSettings() Returns the parameter setting of the attributes.
DistanceFunction<O,D>	getDistanceFunction() Returns the distance function.
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 occured, false otherwise.
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 index sequentially.
void	insert(O object) Inserts the specified object into this M-Tree.
protected void	insert(O object, boolean withPreInsert) todo: do a bulk load for M-Tree and remove this method Inserts the specified object into this M-Tree.
List<QueryResult<D>>	kNNQuery(O object, int k) Performs a k-nearest neighbor query for the given NumberVector with the given parameter k and the according distance function.
protected void	postDelete(O o) Performs necessary operations after deleting the specified object.
List<QueryResult<D>>	rangeQuery(O object, String epsilon) Performs a range query for the given spatial object with the given epsilon range and the according distance function.
List<QueryResult<D>>	reverseKNNQuery(O object, int k) Performs a reverse k-nearest neighbor query for the given object ID.
void	setDatabase(Database<O> database) Sets the databse in the distance function of this index (if existing).
String[]	setParameters(String[] args) Sets the attributes of the class accordingly to the given parameters.
private AbstractMTree.SplitResult	split(N node) Splits the specified node and returns the split result.
String	toString() Returns a string representation of this RTree.

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

close, createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, description, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeFromFile, preInsert, 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

Field Detail

DEFAULT_DISTANCE_FUNCTION

public static final String DEFAULT_DISTANCE_FUNCTION

The default distance function.

DISTANCE_FUNCTION_P

public static final String DISTANCE_FUNCTION_P

Parameter for distance function.

See Also:

Constant Field Values

DISTANCE_FUNCTION_D

public static final String DISTANCE_FUNCTION_D

Description for parameter distance function.

distanceFunction

private DistanceFunction<O extends DatabaseObject,D extends Distance<D>> distanceFunction

The distance function.

Constructor Detail

AbstractMTree

public AbstractMTree()

Empty constructor.

Method Detail

insert

public void insert(O object)

Inserts the specified object into this M-Tree.

Parameters:

object - the object to be inserted todo: in subclasses

insert

public void insert(List<O> objects)

Inserts the specified objects into this index sequentially.

todo: in subclasses todo: bulk load method

Parameters:

objects - the objects to be inserted

delete

public final boolean delete(O o)

Deletes the specified obect from this index.

Parameters:

o - the object to be deleted

Returns:

true if this index did contain the object, false otherwise

postDelete

protected final void postDelete(O o)

Performs necessary operations after deleting the specified object.

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

rangeQuery

public List<QueryResult<D>> rangeQuery(O object,
                                       String epsilon)

Performs a range query for the given spatial 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 List<QueryResult<D>> kNNQuery(O object,
                                     int k)

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.

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

reverseKNNQuery

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

Performs a reverse k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.

Specified by:

reverseKNNQuery 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()

Returns the distance function.

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

toString

public String toString()

Returns a string representation of this RTree.

Overrides:

toString in class Object

Returns:

a string representation of this RTree

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Description copied from interface: Parameterizable

Sets the attributes of the class accordingly to the given parameters. Returns a new String array containing those entries of the given array that are neither expected nor used by this Parameterizable.

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:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

getAttributeSettings

public List<AttributeSettings> getAttributeSettings()

Returns the parameter setting of the attributes.

Specified by:

getAttributeSettings in interface Parameterizable

Overrides:

getAttributeSettings in class AbstractParameterizable

Returns:

the parameter setting of the attributes

See Also:

Parameterizable.getAttributeSettings()

setDatabase

public final void setDatabase(Database<O> database)

Sets the databse in the distance function of this index (if existing).

Parameters:

database - the database

insert

protected void insert(O object,
                      boolean withPreInsert)

todo: do a bulk load for M-Tree and remove this method 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

See Also:

TreeIndex.createEmptyRoot(de.lmu.ifi.dbs.elki.data.DatabaseObject)

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

protected 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 obbject to be inserted

Returns:

the path of the appropriate subtree to insert the given object todo: private?

batchNN

protected final void batchNN(N node,
                             List<Integer> ids,
                             Map<Integer,KNNList<D>> knnLists)

Performs a batch knn query.

Parameters:

node - the node for which the query should be performed

ids - the ids of th query objects

knnLists - the knn lists of the query objcets

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,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

See Also:

TreeIndex.initializeCapacities(DatabaseObject,boolean)

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

createNewLeafEntry

protected abstract E createNewLeafEntry(O object,
                                        D parentDistance)

Creates a new leaf entry representing the specified data object in the specified subtree.

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<QueryResult<D>> result)

Performs a range query. It starts from the root node and recursively traverses all paths, which cannot be excluded from leading to qualififying 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 occured, false otherwise.

Parameters:

node - the node to be tested for overflow

Returns:

true if in the specified node an overflow has occured, 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

distance

protected 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