Class MkAppTree<O>
- java.lang.Object
-
- elki.index.tree.IndexTree<N,E>
-
- elki.index.tree.metrical.MetricalIndexTree<O,N,E>
-
- elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>
-
- elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>
-
- elki.index.tree.metrical.mtreevariants.mktrees.mkapp.MkAppTree<O>
-
- Type Parameters:
O
- the type of DatabaseObject to be stored in the metrical index
- All Implemented Interfaces:
Index
- Direct Known Subclasses:
MkAppTreeIndex
public abstract class MkAppTree<O> extends AbstractMkTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>
MkAppTree is a metrical index structure based on the concepts of the M-Tree supporting efficient processing of reverse k nearest neighbor queries for parameter k < kmax.- Since:
- 0.1
- Author:
- Elke Achtert
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree
AbstractMTree.Statistics
-
-
Field Summary
Fields Modifier and Type Field Description private static Logging
LOG
The logger for this class.-
Fields inherited from class elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree
knnq
-
Fields inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree
settings, statistics
-
Fields inherited from class elki.index.tree.IndexTree
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
-
-
Constructor Summary
Constructors Constructor Description MkAppTree(Relation<O> relation, PageFile<MkAppTreeNode<O>> pageFile, MkAppTreeSettings<O> settings)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
adjustApproximatedKNNDistances(MkAppEntry entry, java.util.Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.private PolynomialApproximation
approximateKnnDistances(double[] knnDistances)
Computes the polynomial approximation of the specified knn-distances.protected MkAppEntry
createNewDirectoryEntry(MkAppTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.protected MkAppTreeNode<O>
createNewDirectoryNode()
Creates a new directory node with the specified capacity.protected MkAppTreeNode<O>
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 double[]
getMeanKNNList(DBIDs ids, java.util.Map<DBID,KNNList> 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(java.util.List<MkAppEntry> entries)
Inserts the specified objects into this MkApp-Tree.private void
leafEntryIDs(MkAppTreeNode<O> 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.DoubleDBIDList
reverseKNNQuery(DBIDRef id, int k)
Performs a reverse k-nearest neighbor query for the given object ID.-
Methods inherited from class elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree
batchNN, distance
-
Methods inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree
createEmptyRoot, distance, doExtraIntegrityChecks, getDistance, getHeight, getLeaves, getSortedEntries, logStatistics, toString
-
Methods inherited from class elki.index.tree.IndexTree
createHeader, deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
-
Constructor Detail
-
MkAppTree
public MkAppTree(Relation<O> relation, PageFile<MkAppTreeNode<O>> pageFile, MkAppTreeSettings<O> settings)
Constructor.- Parameters:
relation
- Relation to indexpageFile
- Page filesettings
- Tree settings
-
-
Method Detail
-
insert
public void insert(MkAppEntry id, boolean withPreInsert)
Description copied from class:AbstractMTree
Inserts the specified object into this M-Tree.- Overrides:
insert
in classAbstractMTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>
- Parameters:
id
- the entry to be insertedwithPreInsert
- if this flag is true, the preInsert method will be called before inserting the object- Throws:
java.lang.UnsupportedOperationException
- since this operation is not supported
-
preInsert
protected void preInsert(MkAppEntry entry)
Description copied from class:IndexTree
Performs necessary operations before inserting the specified entry.- Overrides:
preInsert
in classIndexTree<MkAppTreeNode<O>,MkAppEntry>
- Parameters:
entry
- the entry to be inserted- Throws:
java.lang.UnsupportedOperationException
- since this operation is not supported
-
insertAll
public void insertAll(java.util.List<MkAppEntry> entries)
Inserts the specified objects into this MkApp-Tree.- Overrides:
insertAll
in classAbstractMTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>
- Parameters:
entries
- the entries to be inserted
-
reverseKNNQuery
public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k)
Performs a reverse k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.- Specified by:
reverseKNNQuery
in classAbstractMkTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>
- Parameters:
id
- the query object idk
- the number of nearest neighbors to be returned- Returns:
- a List of the query results
-
getK_max
public int getK_max()
Returns the value of the k_max parameter.- Returns:
- the value of the k_max parameter
-
initializeCapacities
protected void initializeCapacities(MkAppEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.- Specified by:
initializeCapacities
in classIndexTree<MkAppTreeNode<O>,MkAppEntry>
- Parameters:
exampleLeaf
- an object that will be stored in the index
-
adjustApproximatedKNNDistances
private void adjustApproximatedKNNDistances(MkAppEntry entry, java.util.Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.- Parameters:
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entry
-
leafEntryIDs
private void leafEntryIDs(MkAppTreeNode<O> node, ModifiableDBIDs result)
Determines the ids of the leaf entries stored in the specified subtree.- Parameters:
node
- the root of the subtreeresult
- the result list containing the ids of the leaf entries stored in the specified subtree
-
approximateKnnDistances
private PolynomialApproximation approximateKnnDistances(double[] knnDistances)
Computes the polynomial approximation of the specified knn-distances.- Parameters:
knnDistances
- the knn-distances of the leaf entry- Returns:
- the polynomial approximation of the specified knn-distances.
-
createNewLeafNode
protected MkAppTreeNode<O> createNewLeafNode()
Creates a new leaf node with the specified capacity.- Specified by:
createNewLeafNode
in classIndexTree<MkAppTreeNode<O>,MkAppEntry>
- Returns:
- a new leaf node
-
createNewDirectoryNode
protected MkAppTreeNode<O> createNewDirectoryNode()
Creates a new directory node with the specified capacity.- Specified by:
createNewDirectoryNode
in classIndexTree<MkAppTreeNode<O>,MkAppEntry>
- Returns:
- a new directory node
-
createNewDirectoryEntry
protected MkAppEntry createNewDirectoryEntry(MkAppTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.- Specified by:
createNewDirectoryEntry
in classAbstractMTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>
- Parameters:
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 node- Returns:
- the newly created directory entry
-
createRootEntry
protected MkAppEntry createRootEntry()
Creates an entry representing the root node.- Specified by:
createRootEntry
in classIndexTree<MkAppTreeNode<O>,MkAppEntry>
- Returns:
- an entry representing the root node
-
getLogger
protected Logging getLogger()
Description copied from class:IndexTree
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classIndexTree<MkAppTreeNode<O>,MkAppEntry>
- Returns:
- the static logger
-
-