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,MkAppTreeSettings<O,D>>
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 |
---|
MkAppTree(Relation<O> relation,
PageFile<MkAppTreeNode<O,D>> pageFile,
MkAppTreeSettings<O,D> settings)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
private void |
adjustApproximatedKNNDistances(MkAppEntry 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 |
createNewDirectoryEntry(MkAppTreeNode<O,D> node,
DBID routingObjectID,
double 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 |
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,KNNList<D>> knnLists) |
protected void |
initializeCapacities(MkAppEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
void |
insert(MkAppEntry id,
boolean withPreInsert)
Inserts the specified object into this M-Tree.
|
void |
insertAll(List<MkAppEntry> 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 entry)
Performs necessary operations before inserting the specified entry.
|
DistanceDBIDList<D> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
batchNN, distance
createEmptyRoot, distance, getDistanceFactory, getDistanceFunction, getHeight, getLeaves, getSortedEntries, logStatistics, toString
createHeader, deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging LOG
public MkAppTree(Relation<O> relation, PageFile<MkAppTreeNode<O,D>> pageFile, MkAppTreeSettings<O,D> settings)
relation
- Relation to indexpageFile
- Page filesettings
- Tree settingspublic void insert(MkAppEntry id, boolean withPreInsert)
AbstractMTree
insert
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry,MkAppTreeSettings<O,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 entry)
IndexTree
preInsert
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry>
entry
- the entry to be insertedUnsupportedOperationException
- since this operation is not supportedpublic void insertAll(List<MkAppEntry> entries)
insertAll
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry,MkAppTreeSettings<O,D extends NumberDistance<D,?>>>
entries
- the entries to be insertedpublic DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k)
reverseKNNQuery
in class AbstractMkTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry,MkAppTreeSettings<O,D extends NumberDistance<D,?>>>
id
- the query object idk
- the number of nearest neighbors to be returnedpublic int getK_max()
protected void initializeCapacities(MkAppEntry exampleLeaf)
initializeCapacities
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry>
exampleLeaf
- an object that will be stored in the indexprivate void adjustApproximatedKNNDistances(MkAppEntry 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>
protected MkAppTreeNode<O,D> createNewDirectoryNode()
createNewDirectoryNode
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry>
protected MkAppEntry createNewDirectoryEntry(MkAppTreeNode<O,D> node, DBID routingObjectID, double parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry,MkAppTreeSettings<O,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 createRootEntry()
createRootEntry
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry>
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry>