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

Class MkAppTree<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,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp.MkAppTree<O>

Type Parameters:

O - the type of DatabaseObject to be stored in the metrical index

All Implemented Interfaces:

Index, Result

Direct Known Subclasses:

MkAppTreeIndex

public abstract class MkAppTree<O>
extends AbstractMkTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>

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

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
MkAppTree(Relation<O> relation, PageFile<MkAppTreeNode<O>> pageFile, MkAppTreeSettings<O> settings) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private void	adjustApproximatedKNNDistances(MkAppEntry entry, Map<DBID,KNNList> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
private PolynomialApproximation	approximateKnnDistances(double[] knnDistances) Computes the polynomial approximation of the specified knn-distances.
protected MkAppEntry	createNewDirectoryEntry(MkAppTreeNode<O> node, DBID routingObjectID, double parentDistance) Creates a new directory entry representing the specified node.
protected MkAppTreeNode<O>	createNewDirectoryNode() Creates a new directory node with the specified capacity.
protected MkAppTreeNode<O>	createNewLeafNode() Creates a new leaf node with the specified capacity.
protected MkAppEntry	createRootEntry() Creates an entry representing the root node.
int	getK_max() Returns the value of the k_max parameter.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private double[]	getMeanKNNList(DBIDs ids, Map<DBID,KNNList> knnLists)
protected void	initializeCapacities(MkAppEntry exampleLeaf) Determines the maximum and minimum number of entries in a node.
void	insert(MkAppEntry id, boolean withPreInsert) Inserts the specified object into this M-Tree.
void	insertAll(List<MkAppEntry> entries) Inserts the specified objects into this MkApp-Tree.
private void	leafEntryIDs(MkAppTreeNode<O> node, ModifiableDBIDs result) Determines the ids of the leaf entries stored in the specified subtree.
protected void	preInsert(MkAppEntry 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.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

createHeader, 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

MkAppTree

public MkAppTree(Relation<O> relation,
         PageFile<MkAppTreeNode<O>> pageFile,
         MkAppTreeSettings<O> settings)

Constructor.

Parameters:

relation - Relation to index

pageFile - Page file

settings - Tree settings

Method Detail

insert

public void insert(MkAppEntry id,
          boolean withPreInsert)

Description copied from class: AbstractMTree

Inserts the specified object into this M-Tree.

Overrides:

insert in class AbstractMTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>

Parameters:

id - the entry to be inserted

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

Throws:

UnsupportedOperationException - since this operation is not supported

preInsert

protected void preInsert(MkAppEntry entry)

Description copied from class: IndexTree

Performs necessary operations before inserting the specified entry.

Overrides:

preInsert in class IndexTree<MkAppTreeNode<O>,MkAppEntry>

Parameters:

entry - the entry to be inserted

Throws:

UnsupportedOperationException - since this operation is not supported

insertAll

public void insertAll(List<MkAppEntry> entries)

Inserts the specified objects into this MkApp-Tree.

Overrides:

insertAll in class AbstractMTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>

Parameters:

entries - the entries to be inserted

reverseKNNQuery

public DoubleDBIDList reverseKNNQuery(DBIDRef id,
                             int k)

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,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

getK_max

public int getK_max()

Returns the value of the k_max parameter.

Returns:

the value of the k_max parameter

initializeCapacities

protected void initializeCapacities(MkAppEntry exampleLeaf)

Determines the maximum and minimum number of entries in a node.

Specified by:

initializeCapacities in class IndexTree<MkAppTreeNode<O>,MkAppEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

getMeanKNNList

private double[] getMeanKNNList(DBIDs ids,
                      Map<DBID,KNNList> knnLists)

adjustApproximatedKNNDistances

private void adjustApproximatedKNNDistances(MkAppEntry entry,
                                  Map<DBID,KNNList> knnLists)

Adjusts the knn distance in the subtree of the specified root entry.

Parameters:

entry - the root entry of the current subtree

knnLists - a map of knn lists for each leaf entry

leafEntryIDs

private void leafEntryIDs(MkAppTreeNode<O> node,
                ModifiableDBIDs result)

Determines the ids of the leaf entries stored in the specified subtree.

Parameters:

node - the root of the subtree

result - the result list containing the ids of the leaf entries stored in the specified subtree

approximateKnnDistances

private PolynomialApproximation approximateKnnDistances(double[] knnDistances)

Computes the polynomial approximation of the specified knn-distances.

Parameters:

knnDistances - the knn-distances of the leaf entry

Returns:

the polynomial approximation of the specified knn-distances.

createNewLeafNode

protected MkAppTreeNode<O> createNewLeafNode()

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<MkAppTreeNode<O>,MkAppEntry>

Returns:

a new leaf node

createNewDirectoryNode

protected MkAppTreeNode<O> createNewDirectoryNode()

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<MkAppTreeNode<O>,MkAppEntry>

Returns:

a new directory node

createNewDirectoryEntry

protected MkAppEntry createNewDirectoryEntry(MkAppTreeNode<O> node,
                                 DBID routingObjectID,
                                 double parentDistance)

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O,MkAppTreeNode<O>,MkAppEntry,MkAppTreeSettings<O>>

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 MkAppEntry createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<MkAppTreeNode<O>,MkAppEntry>

Returns:

an entry representing the root node

getLogger

protected Logging getLogger()

Description copied from class: IndexTree

Get the (STATIC) logger for this class.

Specified by:

getLogger in class IndexTree<MkAppTreeNode<O>,MkAppEntry>

Returns:

the static logger