Class MkMaxTree<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,N,E,S>
-
- elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
-
- elki.index.tree.metrical.mtreevariants.mktrees.mkmax.MkMaxTree<O>
-
- Type Parameters:
O
- the type of DatabaseObject to be stored in the MkMaxTree
- All Implemented Interfaces:
Index
- Direct Known Subclasses:
MkMaxTreeIndex
public abstract class MkMaxTree<O> extends AbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
MkMaxTree 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 <= k_max. The k-nearest neighbor distance for k = k_max is stored in each entry of a node.- Since:
- 0.2
- 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 MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O>> pagefile, MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry> settings)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected MkMaxEntry
createNewDirectoryEntry(MkMaxTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.protected MkMaxTreeNode<O>
createNewDirectoryNode()
Creates a new directory node with the specified capacity.protected MkMaxTreeNode<O>
createNewLeafNode()
Creates a new leaf node with the specified capacity.protected MkMaxEntry
createRootEntry()
Creates an entry representing the root node.private void
doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O> node, MkMaxEntry node_entry, ModifiableDoubleDBIDList result)
Performs a reverse k-nearest neighbor query in the specified subtree for the given query object with k =AbstractMkTreeUnified.getKmax()
.protected Logging
getLogger()
Get the (STATIC) logger for this class.protected void
initializeCapacities(MkMaxEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.protected void
kNNdistanceAdjustment(MkMaxEntry entry, java.util.Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.protected void
preInsert(MkMaxEntry entry)
Adapts the knn distances before insertion of the specified entry.private void
preInsert(MkMaxEntry q, MkMaxEntry nodeEntry, KNNHeap knns_q)
Adapts the knn distances before insertion of entry q.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.AbstractMkTreeUnified
createHeader, getKmax, insertAll
-
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, insert, logStatistics, toString
-
Methods inherited from class elki.index.tree.IndexTree
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
-
MkMaxTree
public MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O>> pagefile, MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry> settings)
Constructor.- Parameters:
relation
- Relation to indexpagefile
- Page filesettings
- Tree settings
-
-
Method Detail
-
reverseKNNQuery
public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k)
Performs a reverse k-nearest neighbor query for the given object ID. In the first step the candidates are chosen by performing a reverse k-nearest neighbor query with k =AbstractMkTreeUnified.getKmax()
. Then these candidates are refined in a second step.- Specified by:
reverseKNNQuery
in classAbstractMkTree<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
- Parameters:
id
- the query object idk
- the number of nearest neighbors to be returned- Returns:
- a List of the query results
-
preInsert
protected void preInsert(MkMaxEntry entry)
Adapts the knn distances before insertion of the specified entry.- Overrides:
preInsert
in classIndexTree<MkMaxTreeNode<O>,MkMaxEntry>
- Parameters:
entry
- the entry to be inserted
-
kNNdistanceAdjustment
protected void kNNdistanceAdjustment(MkMaxEntry entry, java.util.Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.- Specified by:
kNNdistanceAdjustment
in classAbstractMkTreeUnified<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
- Parameters:
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entry
-
doReverseKNNQuery
private void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O> node, MkMaxEntry node_entry, ModifiableDoubleDBIDList result)
Performs a reverse k-nearest neighbor query in the specified subtree for the given query object with k =AbstractMkTreeUnified.getKmax()
. It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualifying objects.- Parameters:
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 result
-
preInsert
private void preInsert(MkMaxEntry q, MkMaxEntry nodeEntry, KNNHeap knns_q)
Adapts the knn distances before insertion of entry q.- Parameters:
q
- the entry to be insertednodeEntry
- the entry representing the root of the current subtreeknns_q
- the knns of q
-
initializeCapacities
protected void initializeCapacities(MkMaxEntry exampleLeaf)
Description copied from class:IndexTree
Determines the maximum and minimum number of entries in a node.- Specified by:
initializeCapacities
in classIndexTree<MkMaxTreeNode<O>,MkMaxEntry>
- Parameters:
exampleLeaf
- an object that will be stored in the index
-
createNewLeafNode
protected MkMaxTreeNode<O> createNewLeafNode()
Description copied from class:IndexTree
Creates a new leaf node with the specified capacity.- Specified by:
createNewLeafNode
in classIndexTree<MkMaxTreeNode<O>,MkMaxEntry>
- Returns:
- a new MkMaxTreeNode which is a leaf node
-
createNewDirectoryNode
protected MkMaxTreeNode<O> createNewDirectoryNode()
Description copied from class:IndexTree
Creates a new directory node with the specified capacity.- Specified by:
createNewDirectoryNode
in classIndexTree<MkMaxTreeNode<O>,MkMaxEntry>
- Returns:
- a new MkMaxTreeNode which is a directory node
-
createNewDirectoryEntry
protected MkMaxEntry createNewDirectoryEntry(MkMaxTreeNode<O> node, DBID routingObjectID, double parentDistance)
Description copied from class:AbstractMTree
Creates a new directory entry representing the specified node.- Specified by:
createNewDirectoryEntry
in classAbstractMTree<O,MkMaxTreeNode<O>,MkMaxEntry,MkTreeSettings<O,MkMaxTreeNode<O>,MkMaxEntry>>
- 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:
- a new MkMaxDirectoryEntry representing the specified node
-
createRootEntry
protected MkMaxEntry createRootEntry()
Description copied from class:IndexTree
Creates an entry representing the root node.- Specified by:
createRootEntry
in classIndexTree<MkMaxTreeNode<O>,MkMaxEntry>
- Returns:
- a new MkMaxDirectoryEntry by calling
new MkMaxDirectoryEntry(null, null, 0, null)
-
getLogger
protected Logging getLogger()
Description copied from class:IndexTree
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classIndexTree<MkMaxTreeNode<O>,MkMaxEntry>
- Returns:
- the static logger
-
-