O
- Object typeD
- Distance typepublic class MkTabTree<O,D extends Distance<D>> extends AbstractMkTreeUnified<O,D,MkTabTreeNode<O,D>,MkTabEntry<D>>
Modifier and Type | Field and Description |
---|---|
private static Logging |
logger
The logger for this class.
|
distanceFunction, distanceQuery, extraIntegrityChecks
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor and Description |
---|
MkTabTree(PageFile<MkTabTreeNode<O,D>> pagefile,
DistanceQuery<O,D> distanceQuery,
DistanceFunction<O,D> distanceFunction,
int k_max)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
protected MkTabEntry<D> |
createNewDirectoryEntry(MkTabTreeNode<O,D> node,
DBID routingObjectID,
D parentDistance)
Creates a new directory entry representing the specified node.
|
protected MkTabTreeNode<O,D> |
createNewDirectoryNode()
Creates a new directory node with the specified capacity.
|
protected MkTabTreeNode<O,D> |
createNewLeafNode()
Creates a new leaf node with the specified capacity.
|
protected MkTabEntry<D> |
createRootEntry()
Creates an entry representing the root node.
|
private void |
doReverseKNNQuery(int k,
DBIDRef q,
MkTabEntry<D> node_entry,
MkTabTreeNode<O,D> node,
List<DistanceResultPair<D>> 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<D> exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
private List<D> |
initKnnDistanceList()
Returns a knn distance list with all distances set to null distance.
|
void |
insert(MkTabEntry<D> entry,
boolean withPreInsert)
Inserts the specified object into this M-Tree.
|
protected void |
kNNdistanceAdjustment(MkTabEntry<D> entry,
Map<DBID,KNNHeap<D>> knnLists)
Performs a distance adjustment in the subtree of the specified root entry.
|
private List<D> |
max(List<D> distances1,
List<D> distances2)
Returns an array that holds the maximum values of the both specified arrays
in each index.
|
protected void |
preInsert(MkTabEntry<D> entry)
Performs necessary operations before inserting the specified entry.
|
List<DistanceResultPair<D>> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
createHeader, getKmax, insertAll
batchNN, createEmptyRoot, distance, distance, doKNNQuery, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, toString
deleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging logger
public MkTabTree(PageFile<MkTabTreeNode<O,D>> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction, int k_max)
pagefile
- Page filedistanceQuery
- Distance querydistanceFunction
- Distance functionk_max
- Maximum value for kprotected void preInsert(MkTabEntry<D> entry)
IndexTree
preInsert
in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
entry
- the entry to be insertedUnsupportedOperationException
- since insertion of single objects is
not supportedpublic void insert(MkTabEntry<D> entry, boolean withPreInsert)
AbstractMTree
insert
in class AbstractMTree<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
entry
- the entry to be insertedwithPreInsert
- if this flag is true, the preInsert method will be
called before inserting the objectUnsupportedOperationException
- since insertion of single objects is
not supportedpublic List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k)
AbstractMkTree
reverseKNNQuery
in class AbstractMkTree<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
id
- the query object idk
- the number of nearest neighbors to be returnedprotected void initializeCapacities(MkTabEntry<D> exampleLeaf)
IndexTree
initializeCapacities
in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
exampleLeaf
- an object that will be stored in the indexprotected void kNNdistanceAdjustment(MkTabEntry<D> entry, Map<DBID,KNNHeap<D>> knnLists)
AbstractMkTreeUnified
kNNdistanceAdjustment
in class AbstractMkTreeUnified<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entryprotected MkTabTreeNode<O,D> createNewLeafNode()
IndexTree
createNewLeafNode
in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
protected MkTabTreeNode<O,D> createNewDirectoryNode()
createNewDirectoryNode
in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
protected MkTabEntry<D> createNewDirectoryEntry(MkTabTreeNode<O,D> node, DBID routingObjectID, D parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O,D extends Distance<D>,MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<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 MkTabEntry<D> createRootEntry()
createRootEntry
in class IndexTree<MkTabTreeNode<O,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>
private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry<D> node_entry, MkTabTreeNode<O,D> node, List<DistanceResultPair<D>> result)
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 resultprivate List<D> max(List<D> distances1, List<D> distances2)
distances1
- the first arraydistances2
- the second arrayprivate List<D> initKnnDistanceList()