Class MkTabTree<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,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>
-
- elki.index.tree.metrical.mtreevariants.mktrees.mktab.MkTabTree<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Index
- Direct Known Subclasses:
MkTabTreeIndex
public abstract class MkTabTree<O> extends AbstractMkTreeUnified<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>
MkTabTree 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. All knn distances for k <= kmax are stored in each entry of a node.- 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 MkTabTree(Relation<O> relation, PageFile<MkTabTreeNode<O>> pagefile, MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry> settings)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected MkTabEntry
createNewDirectoryEntry(MkTabTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.protected MkTabTreeNode<O>
createNewDirectoryNode()
Creates a new directory node with the specified capacity.protected MkTabTreeNode<O>
createNewLeafNode()
Creates a new leaf node with the specified capacity.protected MkTabEntry
createRootEntry()
Creates an entry representing the root node.private void
doReverseKNNQuery(int k, DBIDRef q, MkTabEntry node_entry, MkTabTreeNode<O> node, ModifiableDoubleDBIDList result)
Performs a k-nearest neighbor query in the specified subtree for the given query object and the given parameter k.protected Logging
getLogger()
Get the (STATIC) logger for this class.protected void
initializeCapacities(MkTabEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.private double[]
initKnnDistanceList()
Returns a knn distance list with all distances set to null distance.void
insert(MkTabEntry entry, boolean withPreInsert)
Inserts the specified object into this M-Tree.protected void
kNNdistanceAdjustment(MkTabEntry entry, java.util.Map<DBID,KNNList> knnLists)
Performs a distance adjustment in the subtree of the specified root entry.private double[]
max(double[] distances1, double[] distances2)
Returns an array that holds the maximum values of the both specified arrays in each index.protected void
preInsert(MkTabEntry 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.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, 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
-
MkTabTree
public MkTabTree(Relation<O> relation, PageFile<MkTabTreeNode<O>> pagefile, MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry> settings)
Constructor.- Parameters:
relation
- Relationpagefile
- Page filesettings
- Settings
-
-
Method Detail
-
preInsert
protected void preInsert(MkTabEntry entry)
Description copied from class:IndexTree
Performs necessary operations before inserting the specified entry.- Overrides:
preInsert
in classIndexTree<MkTabTreeNode<O>,MkTabEntry>
- Parameters:
entry
- the entry to be inserted- Throws:
java.lang.UnsupportedOperationException
- since insertion of single objects is not supported
-
insert
public void insert(MkTabEntry entry, boolean withPreInsert)
Description copied from class:AbstractMTree
Inserts the specified object into this M-Tree.- Overrides:
insert
in classAbstractMTree<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>
- Parameters:
entry
- 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 insertion of single objects is not supported
-
reverseKNNQuery
public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k)
Description copied from class:AbstractMkTree
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,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>
- Parameters:
id
- the query object idk
- the number of nearest neighbors to be returned- Returns:
- a List of the query results
-
initializeCapacities
protected void initializeCapacities(MkTabEntry exampleLeaf)
Description copied from class:IndexTree
Determines the maximum and minimum number of entries in a node.- Specified by:
initializeCapacities
in classIndexTree<MkTabTreeNode<O>,MkTabEntry>
- Parameters:
exampleLeaf
- an object that will be stored in the index
-
kNNdistanceAdjustment
protected void kNNdistanceAdjustment(MkTabEntry entry, java.util.Map<DBID,KNNList> knnLists)
Description copied from class:AbstractMkTreeUnified
Performs a distance adjustment in the subtree of the specified root entry.- Specified by:
kNNdistanceAdjustment
in classAbstractMkTreeUnified<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>
- Parameters:
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entry
-
createNewLeafNode
protected MkTabTreeNode<O> createNewLeafNode()
Description copied from class:IndexTree
Creates a new leaf node with the specified capacity.- Specified by:
createNewLeafNode
in classIndexTree<MkTabTreeNode<O>,MkTabEntry>
- Returns:
- a new leaf node
-
createNewDirectoryNode
protected MkTabTreeNode<O> createNewDirectoryNode()
Creates a new directory node with the specified capacity.- Specified by:
createNewDirectoryNode
in classIndexTree<MkTabTreeNode<O>,MkTabEntry>
- Returns:
- a new directory node
-
createNewDirectoryEntry
protected MkTabEntry createNewDirectoryEntry(MkTabTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.- Specified by:
createNewDirectoryEntry
in classAbstractMTree<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>
- 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 MkTabEntry createRootEntry()
Creates an entry representing the root node.- Specified by:
createRootEntry
in classIndexTree<MkTabTreeNode<O>,MkTabEntry>
- Returns:
- an entry representing the root node
-
doReverseKNNQuery
private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry node_entry, MkTabTreeNode<O> node, ModifiableDoubleDBIDList result)
Performs a k-nearest neighbor query in the specified subtree for the given query object and the given parameter k. It recursively traverses all paths from the specified node, which cannot be excluded from leading to qualifying objects.- Parameters:
k
- the parameter k of the knn-queryq
- the id of the query objectnode_entry
- the entry representing the nodenode
- the root of the subtreeresult
- the list holding the query result
-
max
private double[] max(double[] distances1, double[] distances2)
Returns an array that holds the maximum values of the both specified arrays in each index.- Parameters:
distances1
- the first arraydistances2
- the second array- Returns:
- an array that holds the maximum values of the both specified arrays in each index
-
initKnnDistanceList
private double[] initKnnDistanceList()
Returns a knn distance list with all distances set to null distance.- Returns:
- a knn distance list with all distances set to null distance
-
getLogger
protected Logging getLogger()
Description copied from class:IndexTree
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classIndexTree<MkTabTreeNode<O>,MkTabEntry>
- Returns:
- the static logger
-
-