O
- the type of DatabaseObject to be stored in the MkMaxTreeD
- the type of Distance used in the MkMaxTreepublic class MkMaxTree<O,D extends NumberDistance<D,?>> extends AbstractMkTreeUnified<O,D,MkMaxTreeNode<O,D>,MkMaxEntry,MkTreeSettings<O,D,MkMaxTreeNode<O,D>,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,D>> pagefile,
MkTreeSettings<O,D,MkMaxTreeNode<O,D>,MkMaxEntry> settings)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
protected MkMaxEntry |
createNewDirectoryEntry(MkMaxTreeNode<O,D> node,
DBID routingObjectID,
double parentDistance)
Creates a new directory entry representing the specified node.
|
protected MkMaxTreeNode<O,D> |
createNewDirectoryNode()
Creates a new directory node with the specified capacity.
|
protected MkMaxTreeNode<O,D> |
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,D> node,
MkMaxEntry node_entry,
ModifiableDistanceDBIDList<D> 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<D>> 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<D> knns_q)
Adapts the knn distances before insertion of entry q.
|
DistanceDBIDList<D> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
createHeader, getKmax, insertAll
batchNN, distance
createEmptyRoot, distance, getDistanceFactory, getDistanceFunction, getHeight, getLeaves, getSortedEntries, insert, logStatistics, toString
deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging LOG
public MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O,D>> pagefile, MkTreeSettings<O,D,MkMaxTreeNode<O,D>,MkMaxEntry> settings)
relation
- Relation to indexpagefile
- Page filesettings
- Tree settingspublic DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k)
AbstractMkTreeUnified.getKmax()
. Then these candidates are refined
in a second step.reverseKNNQuery
in class AbstractMkTree<O,D extends NumberDistance<D,?>,MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry>>
id
- the query object idk
- the number of nearest neighbors to be returnedprotected void preInsert(MkMaxEntry entry)
preInsert
in class IndexTree<MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry>
entry
- the entry to be insertedprotected void kNNdistanceAdjustment(MkMaxEntry entry, Map<DBID,KNNList<D>> knnLists)
kNNdistanceAdjustment
in class AbstractMkTreeUnified<O,D extends NumberDistance<D,?>,MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry>>
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entryprivate void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O,D> node, MkMaxEntry node_entry, ModifiableDistanceDBIDList<D> 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<D> 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,D extends NumberDistance<D,?>>,MkMaxEntry>
exampleLeaf
- an object that will be stored in the indexprotected MkMaxTreeNode<O,D> createNewLeafNode()
IndexTree
createNewLeafNode
in class IndexTree<MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry>
protected MkMaxTreeNode<O,D> createNewDirectoryNode()
IndexTree
createNewDirectoryNode
in class IndexTree<MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry>
protected MkMaxEntry createNewDirectoryEntry(MkMaxTreeNode<O,D> node, DBID routingObjectID, double parentDistance)
AbstractMTree
createNewDirectoryEntry
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkMaxTreeNode<O,D extends NumberDistance<D,?>>,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,D extends NumberDistance<D,?>>,MkMaxEntry>
new MkMaxDirectoryEntry(null, null, 0, null)
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkMaxTreeNode<O,D extends NumberDistance<D,?>>,MkMaxEntry>