Class AbstractMTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,N,E>>
- java.lang.Object
-
- elki.index.tree.IndexTree<N,E>
-
- elki.index.tree.metrical.MetricalIndexTree<O,N,E>
-
- elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>
-
- Type Parameters:
O
- the type of DatabaseObject to be stored in the metrical indexN
- the type of MetricalNode used in the metrical indexE
- the type of MetricalEntry used in the metrical indexS
- the type to store settings in.
- All Implemented Interfaces:
Index
- 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.- Since:
- 0.1
- Author:
- Elke Achtert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
AbstractMTree.Statistics
Class for tracking some statistics.
-
Field Summary
Fields Modifier and Type Field Description private 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 elki.index.tree.IndexTree
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
-
-
Constructor Summary
Constructors Constructor Description AbstractMTree(PageFile<N> pagefile, S settings)
Constructor.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method 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.protected void
doExtraIntegrityChecks()
Perform additional integrity checks.Distance<? super O>
getDistance()
Returns the distance function of this metrical index.int
getHeight()
FIXME: expensive depth computation by following a path.java.util.List<E>
getLeaves()
Returns a list of entries pointing to the leaf nodes of this spatial index.protected java.util.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(java.util.List<E> entries)
Bulk insert.void
logStatistics()
Send statistics to the logger, if enabled.java.lang.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 elki.index.tree.IndexTree
createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, getPageID, getPageSize, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeCapacities, initializeFromFile, isRoot, postDelete, preInsert, writeNode
-
-
-
-
Field Detail
-
EXTRA_INTEGRITY_CHECKS
private 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.
-
-
Method Detail
-
getDistance
public final Distance<? super O> getDistance()
Description copied from class:MetricalIndexTree
Returns the distance function of this metrical index.- Specified by:
getDistance
in classMetricalIndexTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>
- Returns:
- the distance function of this metrical index
-
toString
public java.lang.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 classjava.lang.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 insertedwithPreInsert
- if this flag is true, the preInsert method will be called before inserting the object
-
insertAll
public void insertAll(java.util.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 classIndexTree<N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>
- Parameters:
exampleLeaf
- an object that will be stored in the index
-
getSortedEntries
protected final java.util.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 nodeq
- 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 idid2
- 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 entrye2
- 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 entryroutingObjectID
- the id of the routing object of the nodeparentDistance
- 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 RTreenewNode
- the new split nodefirstRoutingObjectID
- the id of the routing objects of the first child nodesecondRoutingObjectID
- 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 java.util.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 classMetricalIndexTree<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 interface:Index
Send statistics to the logger, if enabled.Note: you must have set the logging level appropriately before initializing the index! Otherwise, the index might not have collected the desired statistics.
- Specified by:
logStatistics
in interfaceIndex
- Overrides:
logStatistics
in classIndexTree<N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>
-
doExtraIntegrityChecks
protected void doExtraIntegrityChecks()
Perform additional integrity checks.
-
-