O
- the type of DatabaseObject to be stored in the MkMaxTreepublic abstract class MkMaxTree<O> extends AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
AbstractMTree.Statistics
Modifier and Type | Field and Description |
---|---|
private static Logging |
LOG
The logger for this class.
|
knnq
EXTRA_INTEGRITY_CHECKS, settings, statistics
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor and Description |
---|
MkMaxTree(Relation<O> relation,
PageFile<MkMaxTreeNode<O>> pagefile,
MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry> settings)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
protected MkMaxEntry |
createNewDirectoryEntry(MkMaxTreeNode<O> node,
DBID routingObjectID,
double parentDistance)
Creates a new directory entry representing the specified node.
|
protected MkMaxTreeNode<O> |
createNewDirectoryNode()
Creates a new directory node with the specified capacity.
|
protected MkMaxTreeNode<O> |
createNewLeafNode()
Creates a new leaf node with the specified capacity.
|
protected MkMaxEntry |
createRootEntry()
Creates an entry representing the root node.
|
private void |
doReverseKNNQuery(DBIDRef q,
MkMaxTreeNode<O> node,
MkMaxEntry node_entry,
ModifiableDoubleDBIDList result)
Performs a reverse k-nearest neighbor query in the specified subtree for
the given query object with k =
AbstractMkTreeUnified.getKmax() . |
protected Logging |
getLogger()
Get the (STATIC) logger for this class.
|
protected void |
initializeCapacities(MkMaxEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
protected void |
kNNdistanceAdjustment(MkMaxEntry entry,
Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.
|
protected void |
preInsert(MkMaxEntry entry)
Adapts the knn distances before insertion of the specified entry.
|
private void |
preInsert(MkMaxEntry q,
MkMaxEntry nodeEntry,
KNNHeap knns_q)
Adapts the knn distances before insertion of entry q.
|
DoubleDBIDList |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
createHeader, getKmax, insertAll
batchNN, distance
createEmptyRoot, distance, getDistanceFunction, getHeight, getLeaves, getSortedEntries, insert, logStatistics, toString
deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
getLongName, getShortName
private static final Logging LOG
public MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O>> pagefile, MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry> settings)
relation
- Relation to indexpagefile
- Page filesettings
- Tree settingspublic DoubleDBIDList reverseKNNQuery(DBIDRef id, int k)
AbstractMkTreeUnified.getKmax()
. Then these candidates are refined
in a second step.reverseKNNQuery
in class AbstractMkTree<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
id
- the query object idk
- the number of nearest neighbors to be returnedprotected void preInsert(MkMaxEntry entry)
preInsert
in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>
entry
- the entry to be insertedprotected void kNNdistanceAdjustment(MkMaxEntry entry, Map<DBID,KNNList> knnLists)
kNNdistanceAdjustment
in class AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entryprivate void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O> node, MkMaxEntry node_entry, ModifiableDoubleDBIDList result)
AbstractMkTreeUnified.getKmax()
. It recursively traverses
all paths from the specified node, which cannot be excluded from leading to
qualifying objects.q
- the id of the query objectnode
- the node of the subtree on which the query is performednode_entry
- the entry representing the noderesult
- the list for the query resultprivate void preInsert(MkMaxEntry q, MkMaxEntry nodeEntry, KNNHeap knns_q)
q
- the entry to be insertednodeEntry
- the entry representing the root of the current subtreeknns_q
- the knns of qprotected void initializeCapacities(MkMaxEntry exampleLeaf)
IndexTree
initializeCapacities
in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>
exampleLeaf
- an object that will be stored in the indexprotected MkMaxTreeNode<O> createNewLeafNode()
IndexTree
createNewLeafNode
in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>
protected MkMaxTreeNode<O> createNewDirectoryNode()
IndexTree
createNewDirectoryNode
in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>
protected MkMaxEntry createNewDirectoryEntry(MkMaxTreeNode<O> node, DBID routingObjectID, double parentDistance)
AbstractMTree
createNewDirectoryEntry
in class AbstractMTree<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
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 nodeprotected MkMaxEntry createRootEntry()
IndexTree
createRootEntry
in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>
new MkMaxDirectoryEntry(null, null, 0, null)
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkMaxTreeNode<O>,MkMaxEntry>
Copyright © 2015 ELKI Development Team, Lehr- und Forschungseinheit für Datenbanksysteme, Ludwig-Maximilians-Universität München. License information.