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 |
LOG
The logger for this class.
|
private QueryStatistic |
rkNNStatistics
Provides some statistics about performed reverse knn-queries.
|
knnqdistanceFunction, distanceQuery, EXTRA_INTEGRITY_CHECKSdirCapacity, 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,
ModifiableDistanceDBIDResult<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,KNNResult<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.
|
DistanceDBIDResult<D> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
createHeader, getKmax, insertAllbatchNNcreateEmptyRoot, distance, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, insert, toStringdeleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNodeprivate static final Logging LOG
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 DistanceDBIDResult<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,KNNResult<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, ModifiableDistanceDBIDResult<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)
IndexTreeinitializeCapacities 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()
IndexTreecreateNewLeafNode in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>protected MkMaxTreeNode<O,D> createNewDirectoryNode()
IndexTreecreateNewDirectoryNode 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)
AbstractMTreecreateNewDirectoryEntry 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()
IndexTreecreateRootEntry in class IndexTree<MkMaxTreeNode<O,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>new MkMaxDirectoryEntry(null, null, 0, null)