de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp
Class MkAppTree<O,D extends NumberDistance<D,?>>

java.lang.Object
  de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>
      de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,D,N,E>
          de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,N,E>
              de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,D,MkAppTreeNode<O,D>,MkAppEntry<D>>
                  de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp.MkAppTree<O,D>

Type Parameters:

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

D - the type of NumberDistance used in the metrical index

Direct Known Subclasses:

MkAppTreeIndex

public class MkAppTree<O,D extends NumberDistance<D,?>>
extends AbstractMkTree<O,D,MkAppTreeNode<O,D>,MkAppEntry<D>>

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.

Field Summary

private int	k_max Parameter k.
private boolean	log Flag log.
private static Logging	logger The logger for this class.
private int	p Parameter p.

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

distanceFunction, distanceQuery, extraIntegrityChecks

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

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

MkAppTree(PageFile<MkAppTreeNode<O,D>> pageFile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction, int k_max, int p, boolean log)
Constructor.

Method Summary

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

batchNN, createEmptyRoot, distance, distance, doKNNQuery, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, toString

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

createHeader, deleteNode, getFile, getNode, getNode, getPageFileStatistics, 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

Field Detail

logger

private static final Logging logger

The logger for this class.

k_max

private int k_max

Parameter k.

p

private int p

Parameter p.

log

private boolean log

Flag log.

Constructor Detail

MkAppTree

public MkAppTree(PageFile<MkAppTreeNode<O,D>> pageFile,
                 DistanceQuery<O,D> distanceQuery,
                 DistanceFunction<O,D> distanceFunction,
                 int k_max,
                 int p,
                 boolean log)

Constructor.

Parameters:

pageFile - Page file

distanceQuery - Distance query

distanceFunction - Distance function

k_max - Maximum value of k supported

p - Parameter p

log - Logspace flag

Method Detail

insert

public void insert(MkAppEntry<D> id,
                   boolean withPreInsert)

Description copied from class: AbstractMTree

Inserts the specified object into this M-Tree.

Overrides:

insert in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

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<D> entry)

Description copied from class: IndexTree

Performs necessary operations before inserting the specified entry.

Overrides:

preInsert in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

Parameters:

entry - the entry to be inserted

Throws:

UnsupportedOperationException - since this operation is not supported

insertAll

public void insertAll(List<MkAppEntry<D>> entries)

Inserts the specified objects into this MkApp-Tree.

Overrides:

insertAll in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

Parameters:

entries - the entries to be inserted

reverseKNNQuery

public List<DistanceResultPair<D>> reverseKNNQuery(DBID 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,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

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<D> exampleLeaf)

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

Specified by:

initializeCapacities in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

Parameters:

exampleLeaf - an object that will be stored in the index

doReverseKNNQuery

private List<DistanceResultPair<D>> doReverseKNNQuery(int k,
                                                      DBID q)

Performs a reverse knn query.

Parameters:

k - the parameter k of the rknn query

q - the id of the query object

Returns:

the result of the reverse knn query

getMeanKNNList

private List<D> getMeanKNNList(DBIDs ids,
                               Map<DBID,KNNList<D>> knnLists)

adjustApproximatedKNNDistances

private void adjustApproximatedKNNDistances(MkAppEntry<D> entry,
                                            Map<DBID,KNNList<D>> 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,D> 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(List<D> 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,D> createNewLeafNode()

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

Returns:

a new leaf node

createNewDirectoryNode

protected MkAppTreeNode<O,D> createNewDirectoryNode()

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

Returns:

a new directory node

createNewDirectoryEntry

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

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O,D extends NumberDistance<D,?>,MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

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

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<MkAppTreeNode<O,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

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,D extends NumberDistance<D,?>>,MkAppEntry<D extends NumberDistance<D,?>>>

Returns:

the static logger