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

Class AbstractMTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

java.lang.Object

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

de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<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

Direct Known Subclasses:

AbstractMkTree, MTree

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

Abstract super class for all M-Tree variants.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	AbstractMTree.SplitResult Encapsulates a split object and the newly created node.

Field Summary

Fields

Modifier and Type	Field and Description
protected DistanceFunction<O,D>	distanceFunction Holds the instance of the trees distance function
protected DistanceQuery<O,D>	distanceQuery The distance query
protected static boolean	extraIntegrityChecks Debugging flag: do extra integrity checks

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, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private void	adjustTree(IndexTreePath<E> subtree) Adjusts the tree after insertion of some nodes.
protected void	batchNN(N node, DBIDs ids, Map<DBID,KNNHeap<D>> knnLists) Deprecated. Change to use by-object NN lookups instead.
private IndexTreePath<E>	choosePath(E object, IndexTreePath<E> subtree) Chooses the best path of the specified subtree for insertion of the given object.
protected void	createEmptyRoot(E exampleLeaf) Creates an empty root node and writes it to file.
protected abstract E	createNewDirectoryEntry(N node, DBID routingObjectID, D 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.
protected D	distance(DBID id1, DBID id2) Returns the distance between the two specified ids.
protected D	distance(DBID id1, O o2) Returns the distance between the given object and the id.
protected void	doKNNQuery(DBID q, KNNHeap<D> knnList) Performs a k-nearest neighbor query for the given FeatureVector with the given parameter k and the according distance function.
protected D	getDistanceFactory() Get the distance factory
DistanceFunction<O,D>	getDistanceFunction() Returns the distance function of this metrical index.
DistanceQuery<O,D>	getDistanceQuery() 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<DistanceEntry<D,E>>	getSortedEntries(N node, DBID 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, DBIDs 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.
void	insert(E entry, boolean withPreInsert) Inserts the specified object into this M-Tree.
void	insertAll(List<E> entries) Bulk insert.
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.IndexTree

createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, getPageFileStatistics, 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

extraIntegrityChecks

protected static final boolean extraIntegrityChecks

Debugging flag: do extra integrity checks

See Also:

Constant Field Values

distanceFunction

protected DistanceFunction<O,D extends Distance<D>> distanceFunction

Holds the instance of the trees distance function

distanceQuery

protected DistanceQuery<O,D extends Distance<D>> distanceQuery

The distance query

Constructor Detail

AbstractMTree

public AbstractMTree(PageFile<N> pagefile,
             DistanceQuery<O,D> distanceQuery,
             DistanceFunction<O,D> distanceFunction)

Constructor.

Parameters:

pagefile - Page file

distanceQuery - Distance query

distanceFunction - Distance function

Method Detail

getDistanceFunction

public final DistanceFunction<O,D> getDistanceFunction()

Description copied from class: MetricalIndexTree

Returns the distance function of this metrical index.

Specified by:

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

Returns:

the distance function of this metrical index

getDistanceQuery

public final DistanceQuery<O,D> getDistanceQuery()

Description copied from class: MetricalIndexTree

Returns the distance function of this metrical index.

Specified by:

getDistanceQuery in class MetricalIndexTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

Returns:

the distance function of this metrical index

getDistanceFactory

protected final D getDistanceFactory()

Get the distance factory

Returns:

the distance factory used

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 -

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

Parameters:

exampleLeaf - an object that will be stored in the index

doKNNQuery

protected final void doKNNQuery(DBID q,
              KNNHeap<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 IndexTreePath<E> choosePath(E object,
                          IndexTreePath<E> subtree)

Chooses the best path of the specified subtree for insertion of the given object.

Parameters:

object - the entry to search

subtree - the subtree to be tested for insertion

Returns:

the path of the appropriate subtree to insert the given object

batchNN

@Deprecated
protected final void batchNN(N node,
                      DBIDs ids,
                      Map<DBID,KNNHeap<D>> knnLists)

Deprecated. Change to use by-object NN lookups instead.

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

getSortedEntries

protected final List<DistanceEntry<D,E>> getSortedEntries(N node,
                                        DBIDs 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(DBID id1,
         DBID 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

protected final D distance(DBID id1,
         O o2)

Returns the distance between the given object and the id.

Parameters:

id1 - the first id

o2 - the second object

Returns:

the distance between the two specified objects

createNewDirectoryEntry

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

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

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