O
- the type of DatabaseObject to be stored in the metrical indexD
- the type of NumberDistance used in the metrical indexpublic class MkAppTree<O,D extends NumberDistance<D,?>> extends AbstractMkTree<O,D,MkAppTreeNode<O,D>,MkAppEntry<D>>
Modifier and Type | Field and Description |
---|---|
private int |
k_max
Parameter k.
|
private boolean |
log
Flag log.
|
private static Logging |
logger
The logger for this class.
|
private int |
p
Parameter p.
|
distanceFunction, distanceQuery, extraIntegrityChecks
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor and Description |
---|
MkAppTree(PageFile<MkAppTreeNode<O,D>> pageFile,
DistanceQuery<O,D> distanceQuery,
DistanceFunction<O,D> distanceFunction,
int k_max,
int p,
boolean log)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
private void |
adjustApproximatedKNNDistances(MkAppEntry<D> entry,
Map<DBID,KNNList<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.
|
private PolynomialApproximation |
approximateKnnDistances(List<D> knnDistances)
Computes the polynomial approximation of the specified knn-distances.
|
protected MkAppEntry<D> |
createNewDirectoryEntry(MkAppTreeNode<O,D> node,
DBID routingObjectID,
D parentDistance)
Creates a new directory entry representing the specified node.
|
protected MkAppTreeNode<O,D> |
createNewDirectoryNode()
Creates a new directory node with the specified capacity.
|
protected MkAppTreeNode<O,D> |
createNewLeafNode()
Creates a new leaf node with the specified capacity.
|
protected MkAppEntry<D> |
createRootEntry()
Creates an entry representing the root node.
|
private List<DistanceResultPair<D>> |
doReverseKNNQuery(int k,
DBIDRef q)
Performs a reverse knn query.
|
int |
getK_max()
Returns the value of the k_max parameter.
|
protected Logging |
getLogger()
Get the (STATIC) logger for this class.
|
private List<D> |
getMeanKNNList(DBIDs ids,
Map<DBID,KNNList<D>> knnLists) |
protected void |
initializeCapacities(MkAppEntry<D> exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
void |
insert(MkAppEntry<D> id,
boolean withPreInsert)
Inserts the specified object into this M-Tree.
|
void |
insertAll(List<MkAppEntry<D>> entries)
Inserts the specified objects into this MkApp-Tree.
|
private void |
leafEntryIDs(MkAppTreeNode<O,D> node,
ModifiableDBIDs result)
Determines the ids of the leaf entries stored in the specified subtree.
|
protected void |
preInsert(MkAppEntry<D> entry)
Performs necessary operations before inserting the specified entry.
|
List<DistanceResultPair<D>> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
batchNN, createEmptyRoot, distance, distance, doKNNQuery, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, toString
createHeader, deleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging logger
private int k_max
private int p
private boolean log
public MkAppTree(PageFile<MkAppTreeNode<O,D>> pageFile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction, int k_max, int p, boolean log)
pageFile
- Page filedistanceQuery
- Distance querydistanceFunction
- Distance functionk_max
- Maximum value of k supportedp
- Parameter plog
- Logspace flagpublic void insert(MkAppEntry<D> id, boolean withPreInsert)
AbstractMTree
insert
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
id
- the entry to be insertedwithPreInsert
- if this flag is true, the preInsert method will be
called before inserting the objectUnsupportedOperationException
- since this operation is not supportedprotected void preInsert(MkAppEntry<D> entry)
IndexTree
preInsert
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
entry
- the entry to be insertedUnsupportedOperationException
- since this operation is not supportedpublic void insertAll(List<MkAppEntry<D>> entries)
insertAll
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
entries
- the entries to be insertedpublic List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k)
reverseKNNQuery
in class AbstractMkTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
id
- the query object idk
- the number of nearest neighbors to be returnedpublic int getK_max()
protected void initializeCapacities(MkAppEntry<D> exampleLeaf)
initializeCapacities
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
exampleLeaf
- an object that will be stored in the indexprivate List<DistanceResultPair<D>> doReverseKNNQuery(int k, DBIDRef q)
k
- the parameter k of the rknn queryq
- the id of the query objectprivate void adjustApproximatedKNNDistances(MkAppEntry<D> entry, Map<DBID,KNNList<D>> knnLists)
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entryprivate void leafEntryIDs(MkAppTreeNode<O,D> node, ModifiableDBIDs result)
node
- the root of the subtreeresult
- the result list containing the ids of the leaf entries stored
in the specified subtreeprivate PolynomialApproximation approximateKnnDistances(List<D> knnDistances)
knnDistances
- the knn-distances of the leaf entryprotected MkAppTreeNode<O,D> createNewLeafNode()
createNewLeafNode
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
protected MkAppTreeNode<O,D> createNewDirectoryNode()
createNewDirectoryNode
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
protected MkAppEntry<D> createNewDirectoryEntry(MkAppTreeNode<O,D> node, DBID routingObjectID, D parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<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 MkAppEntry<D> createRootEntry()
createRootEntry
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>