O
- the type of DatabaseObject to be stored in the MkMaxTreeD
- the type of Distance used in the MkMaxTreepublic class MkMaxTree<O,D extends Distance<D>> extends AbstractMkTreeUnified<O,D,MkMaxTreeNode<O,D>,MkMaxEntry<D>>
Modifier and Type | Field and Description |
---|---|
private static Logging |
logger
The logger for this class.
|
private QueryStatistic |
rkNNStatistics
Provides some statistics about performed reverse knn-queries.
|
distanceFunction, distanceQuery, extraIntegrityChecks
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor and Description |
---|
MkMaxTree(PageFile<MkMaxTreeNode<O,D>> pagefile,
DistanceQuery<O,D> distanceQuery,
DistanceFunction<O,D> distanceFunction,
int k_max)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
void |
clearRkNNStatistics()
Clears the values of the statistic for performed rknn queries
|
protected MkMaxEntry<D> |
createNewDirectoryEntry(MkMaxTreeNode<O,D> node,
DBID routingObjectID,
D 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<D> |
createRootEntry()
Creates an entry representing the root node.
|
private void |
doReverseKNNQuery(DBIDRef q,
MkMaxTreeNode<O,D> node,
MkMaxEntry<D> node_entry,
List<DistanceResultPair<D>> result)
Performs a reverse k-nearest neighbor query in the specified subtree for
the given query object with k =
AbstractMkTreeUnified.k_max . |
protected Logging |
getLogger()
Get the (STATIC) logger for this class.
|
QueryStatistic |
getRkNNStatistics()
Returns the statistic for performed rknn queries.
|
protected void |
initializeCapacities(MkMaxEntry<D> exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
protected void |
kNNdistanceAdjustment(MkMaxEntry<D> entry,
Map<DBID,KNNHeap<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.
|
protected void |
preInsert(MkMaxEntry<D> entry)
Adapts the knn distances before insertion of the specified entry.
|
private void |
preInsert(MkMaxEntry<D> q,
MkMaxEntry<D> nodeEntry,
KNNHeap<D> knns_q)
Adapts the knn distances before insertion of entry q.
|
List<DistanceResultPair<D>> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
createHeader, getKmax, insertAll
batchNN, createEmptyRoot, distance, distance, doKNNQuery, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, insert, toString
deleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging logger
private QueryStatistic rkNNStatistics
public MkMaxTree(PageFile<MkMaxTreeNode<O,D>> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction, int k_max)
pagefile
- Page filedistanceQuery
- Distance querydistanceFunction
- Distance functionk_max
- Maximum value for kpublic List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k)
AbstractMkTreeUnified.k_max
. Then these candidates are refined
in a second step.reverseKNNQuery
in class AbstractMkTree<O,D extends Distance<D>,MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
id
- the query object idk
- the number of nearest neighbors to be returnedpublic QueryStatistic getRkNNStatistics()
public void clearRkNNStatistics()
protected void preInsert(MkMaxEntry<D> entry)
protected void kNNdistanceAdjustment(MkMaxEntry<D> entry, Map<DBID,KNNHeap<D>> knnLists)
kNNdistanceAdjustment
in class AbstractMkTreeUnified<O,D extends Distance<D>,MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
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<D> node_entry, List<DistanceResultPair<D>> result)
AbstractMkTreeUnified.k_max
. It recursively traverses
all paths from the specified node, which cannot be excluded from leading to
qualififying 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<D> q, MkMaxEntry<D> nodeEntry, KNNHeap<D> knns_q)
q
- the entry to be insertednodeEntry
- the entry representing the root of thge current subtreeknns_q
- the knns of qprotected void initializeCapacities(MkMaxEntry<D> exampleLeaf)
IndexTree
initializeCapacities
in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
exampleLeaf
- an object that will be stored in the indexprotected MkMaxTreeNode<O,D> createNewLeafNode()
IndexTree
createNewLeafNode
in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
protected MkMaxTreeNode<O,D> createNewDirectoryNode()
IndexTree
createNewDirectoryNode
in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
protected MkMaxEntry<D> createNewDirectoryEntry(MkMaxTreeNode<O,D> node, DBID routingObjectID, D parentDistance)
AbstractMTree
createNewDirectoryEntry
in class AbstractMTree<O,D extends Distance<D>,MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
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<D> createRootEntry()
IndexTree
createRootEntry
in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>
new MkMaxDirectoryEntry(null, null, 0, null)