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

Class AbstractMTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,N,E>>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>

Type Parameters:

O - the type of DatabaseObject to be stored in the metrical index

N - the type of MetricalNode used in the metrical index

E - the type of MetricalEntry used in the metrical index

S - the type to store settings in.

Direct Known Subclasses:

AbstractMkTree, MTree

public abstract class AbstractMTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,N,E>>
extends MetricalIndexTree<O,N,E>

Abstract super class for all M-Tree variants.

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	AbstractMTree.Statistics Class for tracking some statistics.

Field Summary

Fields

Modifier and Type	Field and Description
protected static boolean	EXTRA_INTEGRITY_CHECKS Debugging flag: do extra integrity checks.
protected S	settings Tree settings.
AbstractMTree.Statistics	statistics For counting the number of distance computations.

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
AbstractMTree(PageFile<N> pagefile, S settings) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	adjustTree(IndexTreePath<E> subtree) Adjusts the tree after insertion of some nodes.
protected void	createEmptyRoot(E exampleLeaf) Creates an empty root node and writes it to file.
protected abstract E	createNewDirectoryEntry(N node, DBID routingObjectID, double parentDistance) Creates a new directory entry representing the specified node.
private IndexTreePath<E>	createNewRoot(N oldRoot, N newNode, DBID firstRoutingObjectID, DBID secondRoutingObjectID) Creates a new root node that points to the two specified child nodes and return the path to the new root.
abstract double	distance(DBIDRef id1, DBIDRef id2) Returns the distance between the two specified ids.
double	distance(E e1, E e2) Returns the distance between the routing object of two entries.
DistanceFunction<? super O>	getDistanceFunction() Returns the distance function of this metrical index.
int	getHeight() FIXME: expensive depth computation by following a path.
List<E>	getLeaves() Returns a list of entries pointing to the leaf nodes of this spatial index.
protected List<DoubleIntPair>	getSortedEntries(N node, DBID q) Sorts the entries of the specified node according to their minimum distance to the specified object.
private boolean	hasOverflow(N node) Returns true if in the specified node an overflow has occurred, false otherwise.
void	insert(E entry, boolean withPreInsert) Inserts the specified object into this M-Tree.
void	insertAll(List<E> entries) Bulk insert.
void	logStatistics() Log some statistics, if enabled.
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.IndexTree

createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeCapacities, initializeFromFile, isRoot, postDelete, preInsert, writeNode

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

EXTRA_INTEGRITY_CHECKS

protected static final boolean EXTRA_INTEGRITY_CHECKS

Debugging flag: do extra integrity checks.

See Also:

Constant Field Values

settings

protected S extends MTreeSettings<O,N,E> settings

Tree settings.

statistics

public AbstractMTree.Statistics statistics

For counting the number of distance computations.

Constructor Detail

AbstractMTree

public AbstractMTree(PageFile<N> pagefile,
                     S settings)

Constructor.

Parameters:

pagefile - Page file

settings - Tree settings

Method Detail

getDistanceFunction

public final DistanceFunction<? super O> getDistanceFunction()

Description copied from class: MetricalIndexTree

Returns the distance function of this metrical index.

Specified by:

getDistanceFunction in class MetricalIndexTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>

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

insert

public void insert(E entry,
                   boolean withPreInsert)

Inserts the specified object into this M-Tree.

Parameters:

entry - the entry to be inserted

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

insertAll

public void insertAll(List<E> entries)

Bulk insert.

Parameters:

entries - Entries to insert

createEmptyRoot

protected final void createEmptyRoot(E exampleLeaf)

Description copied from class: IndexTree

Creates an empty root node and writes it to file.

Specified by:

createEmptyRoot in class IndexTree<N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

getSortedEntries

protected final List<DoubleIntPair> getSortedEntries(N node,
                                                     DBID 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

distance

public abstract double distance(DBIDRef id1,
                                DBIDRef 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

distance

public final double distance(E e1,
                             E e2)

Returns the distance between the routing object of two entries.

Parameters:

e1 - First entry

e2 - Second entry

Returns:

the distance between the two routing objects

createNewDirectoryEntry

protected abstract E createNewDirectoryEntry(N node,
                                             DBID routingObjectID,
                                             double 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

adjustTree

private void adjustTree(IndexTreePath<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 IndexTreePath<E> createNewRoot(N oldRoot,
                                       N newNode,
                                       DBID firstRoutingObjectID,
                                       DBID 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

getLeaves

public List<E> getLeaves()

Description copied from class: MetricalIndexTree

Returns a list of entries pointing to the leaf nodes of this spatial index.

Specified by:

getLeaves in class MetricalIndexTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>

Returns:

a list of entries pointing to the leaf nodes of this spatial index

getHeight

public int getHeight()

FIXME: expensive depth computation by following a path.

Returns:

depth

logStatistics

public void logStatistics()

Description copied from class: IndexTree

Log some statistics, if enabled.

Overrides:

logStatistics in class IndexTree<N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>