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
  extended by de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>
      extended by de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<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
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
private  class AbstractMTree.SplitResult
          Encapsulates a split object and the newly created node.
 
Field Summary
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
AbstractMTree(PageFile<N> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction)
          Constructor.
 
Method Summary
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

Release 0.4.0 (2011-09-20_1324)