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 |
LOG
The logger for this class.
|
private int |
p
Parameter p.
|
knnq
distanceFunction, distanceQuery, EXTRA_INTEGRITY_CHECKS
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,KNNResult<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.
|
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,KNNResult<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.
|
DistanceDBIDResult<D> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
batchNN
createEmptyRoot, distance, 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 LOG
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 DistanceDBIDResult<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 void adjustApproximatedKNNDistances(MkAppEntry<D> entry, Map<DBID,KNNResult<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,?>>>