O
- Object typeD
- Distance typepublic class MkTabTree<O,D extends NumberDistance<D,?>> extends AbstractMkTreeUnified<O,D,MkTabTreeNode<O,D>,MkTabEntry,MkTreeSettings<O,D,MkTabTreeNode<O,D>,MkTabEntry>>
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 |
---|
MkTabTree(Relation<O> relation,
PageFile<MkTabTreeNode<O,D>> pagefile,
MkTreeSettings<O,D,MkTabTreeNode<O,D>,MkTabEntry> settings)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
protected MkTabEntry |
createNewDirectoryEntry(MkTabTreeNode<O,D> node,
DBID routingObjectID,
double 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 |
createRootEntry()
Creates an entry representing the root node.
|
private void |
doReverseKNNQuery(int k,
DBIDRef q,
MkTabEntry node_entry,
MkTabTreeNode<O,D> node,
GenericDistanceDBIDList<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 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,
Map<DBID,KNNList<D>> 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.
|
DistanceDBIDList<D> |
reverseKNNQuery(DBIDRef id,
int k)
Performs a reverse k-nearest neighbor query for the given object ID.
|
createHeader, getKmax, insertAll
batchNN, distance
createEmptyRoot, distance, getDistanceFactory, getDistanceFunction, getHeight, getLeaves, getSortedEntries, logStatistics, toString
deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging LOG
public MkTabTree(Relation<O> relation, PageFile<MkTabTreeNode<O,D>> pagefile, MkTreeSettings<O,D,MkTabTreeNode<O,D>,MkTabEntry> settings)
relation
- Relationpagefile
- Page filesettings
- Settingsprotected void preInsert(MkTabEntry entry)
IndexTree
preInsert
in class IndexTree<MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>
entry
- the entry to be insertedUnsupportedOperationException
- since insertion of single objects is
not supportedpublic void insert(MkTabEntry entry, boolean withPreInsert)
AbstractMTree
insert
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>>
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 DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k)
AbstractMkTree
reverseKNNQuery
in class AbstractMkTree<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>>
id
- the query object idk
- the number of nearest neighbors to be returnedprotected void initializeCapacities(MkTabEntry exampleLeaf)
IndexTree
initializeCapacities
in class IndexTree<MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>
exampleLeaf
- an object that will be stored in the indexprotected void kNNdistanceAdjustment(MkTabEntry entry, Map<DBID,KNNList<D>> knnLists)
AbstractMkTreeUnified
kNNdistanceAdjustment
in class AbstractMkTreeUnified<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>>
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 NumberDistance<D,?>>,MkTabEntry>
protected MkTabTreeNode<O,D> createNewDirectoryNode()
createNewDirectoryNode
in class IndexTree<MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>
protected MkTabEntry createNewDirectoryEntry(MkTabTreeNode<O,D> node, DBID routingObjectID, double parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>>
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 createRootEntry()
createRootEntry
in class IndexTree<MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>
private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry node_entry, MkTabTreeNode<O,D> node, GenericDistanceDBIDList<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 double[] max(double[] distances1, double[] distances2)
distances1
- the first arraydistances2
- the second arrayprivate double[] initKnnDistanceList()
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkTabTreeNode<O,D extends NumberDistance<D,?>>,MkTabEntry>