de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab

Class MkTabTree<O>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,N,E,S>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab.MkTabTree<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, Result

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.2

Author:

Elke Achtert

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

AbstractMTree.Statistics

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG The logger for this class.

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree

knnq

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

EXTRA_INTEGRITY_CHECKS, settings, statistics

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
MkTabTree(Relation<O> relation, PageFile<MkTabTreeNode<O>> pagefile, MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry> settings) Constructor.

Method Summary

Methods

Modifier and Type	Method and 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, 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 de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified

createHeader, getKmax, insertAll

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree

batchNN, distance

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

createEmptyRoot, distance, getDistanceFunction, getHeight, getLeaves, getSortedEntries, logStatistics, toString

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

getLongName, getShortName

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 - Relation

pagefile - Page file

settings - 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 class IndexTree<MkTabTreeNode<O>,MkTabEntry>

Parameters:

entry - the entry to be inserted

Throws:

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 class AbstractMTree<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>

Parameters:

entry - the entry to be inserted

withPreInsert - if this flag is true, the preInsert method will be called before inserting the object

Throws:

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 class AbstractMkTree<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>

Parameters:

id - the query object id

k - 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 class IndexTree<MkTabTreeNode<O>,MkTabEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

kNNdistanceAdjustment

protected void kNNdistanceAdjustment(MkTabEntry entry,
                         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 class AbstractMkTreeUnified<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>

Parameters:

entry - the root entry of the current subtree

knnLists - 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 class IndexTree<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 class IndexTree<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 class AbstractMTree<O,MkTabTreeNode<O>,MkTabEntry,MkTreeSettings<O,MkTabTreeNode<O>,MkTabEntry>>

Parameters:

node - the node to be represented by the new entry

routingObjectID - the id of the routing object of the node

parentDistance - 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 class IndexTree<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-query

q - the id of the query object

node_entry - the entry representing the node

node - the root of the subtree

result - 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 array

distances2 - 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 class IndexTree<MkTabTreeNode<O>,MkTabEntry>

Returns:

the static logger