|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
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>
O
- the type of DatabaseObject to be stored in the metrical indexD
- the type of Distance used in the metrical indexN
- the type of MetricalNode used in the metrical indexE
- the type of MetricalEntry used in the metrical indexpublic abstract class AbstractMTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
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 |
---|
protected static final boolean extraIntegrityChecks
protected DistanceFunction<O,D extends Distance<D>> distanceFunction
protected DistanceQuery<O,D extends Distance<D>> distanceQuery
Constructor Detail |
---|
public AbstractMTree(PageFile<N> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction)
pagefile
- Page filedistanceQuery
- Distance querydistanceFunction
- Distance functionMethod Detail |
---|
public final DistanceFunction<O,D> getDistanceFunction()
MetricalIndexTree
getDistanceFunction
in class MetricalIndexTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
public final DistanceQuery<O,D> getDistanceQuery()
MetricalIndexTree
getDistanceQuery
in class MetricalIndexTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
protected final D getDistanceFactory()
public String toString()
toString
in class Object
public void insert(E entry, boolean withPreInsert)
entry
- the entry to be insertedwithPreInsert
- if this flag is true, the preInsert method will be
called before inserting the objectpublic void insertAll(List<E> entries)
entries
- protected final void createEmptyRoot(E exampleLeaf)
IndexTree
createEmptyRoot
in class IndexTree<N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
exampleLeaf
- an object that will be stored in the indexprotected final void doKNNQuery(DBID q, KNNHeap<D> knnList)
q
- the id of the query objectknnList
- the query result listprivate IndexTreePath<E> choosePath(E object, IndexTreePath<E> subtree)
object
- the entry to searchsubtree
- the subtree to be tested for insertion
@Deprecated protected final void batchNN(N node, DBIDs ids, Map<DBID,KNNHeap<D>> knnLists)
node
- the node reprsenting the subtree on which the query should be
performedids
- the ids of th query objectsknnLists
- the knn lists of the query objcetsprotected final List<DistanceEntry<D,E>> getSortedEntries(N node, DBID q)
node
- the nodeq
- the id of the object
protected final List<DistanceEntry<D,E>> getSortedEntries(N node, DBIDs ids)
node
- the nodeids
- the ids of the objects
protected final D distance(DBID id1, DBID id2)
id1
- the first idid2
- the second id
protected final D distance(DBID id1, O o2)
id1
- the first ido2
- the second object
protected abstract E createNewDirectoryEntry(N node, DBID routingObjectID, D parentDistance)
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
private AbstractMTree.SplitResult split(N node)
node
- the node to be split
private void adjustTree(IndexTreePath<E> subtree)
subtree
- the subtree to be adjustedprivate boolean hasOverflow(N node)
node
- the node to be tested for overflow
private IndexTreePath<E> createNewRoot(N oldRoot, N newNode, DBID firstRoutingObjectID, DBID secondRoutingObjectID)
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
public List<E> getLeaves()
MetricalIndexTree
getLeaves
in class MetricalIndexTree<O,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
public int getHeight()
|
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |