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

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndex<O,D,N,E>
                  de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,MkAppTreeNode<O,D,N>,MkAppEntry<D,N>>
                      de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp.MkAppTree<O,D,N>

Type Parameters:

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

D - the type of NumberDistance used in the metrical index

N - the type of Number used in the NumberDistance

All Implemented Interfaces:

Index<O>, Parameterizable

public class MkAppTree<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>
extends AbstractMTree<O,D,MkAppTreeNode<O,D,N>,MkAppEntry<D,N>>

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.

Author:

Elke Achtert

Field Summary

static OptionID	K_ID OptionID for K_PARAM
private int	k_max Parameter k.
private IntParameter	K_PARAM Parameter for k
private boolean	log Flag log.
static OptionID	NOLOG_ID OptionID for NOLOG_PARAM
private Flag	NOLOG_PARAM Parameter for nolog
private int	p Parameter p.
static OptionID	P_ID OptionID for P_PARAM
private IntParameter	P_PARAM Parameter for p

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

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM, extraIntegrityChecks

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

CACHE_SIZE_ID, cacheSize, dirCapacity, dirMinimum, file, FILE_ID, initialized, leafCapacity, leafMinimum, PAGE_SIZE_ID, pageSize

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

MkAppTree()
Creates a new MkCopTree.

Method Summary

private void	adjustApproximatedKNNDistances(MkAppEntry<D,N> entry, Map<Integer,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,N>	createNewDirectoryEntry(MkAppTreeNode<O,D,N> node, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkAppTreeNode<O,D,N>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MkAppEntry<D,N>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object in the specified subtree.
protected MkAppTreeNode<O,D,N>	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected MkAppEntry<D,N>	createRootEntry() Creates an entry representing the root node.
private List<DistanceResultPair<D>>	doReverseKNNQuery(int k, Integer q) Performs a reverse knn query.
int	getK_max() Returns the value of the k_max parameter.
private List<D>	getMeanKNNList(List<Integer> ids, Map<Integer,KNNList<D>> knnLists)
protected void	initializeCapacities(O object, boolean verbose) Determines the maximum and minimum number of entries in a node.
void	insert(List<O> objects) Inserts the specified objects into this MkApp-Tree.
void	insert(O object) Inserts the specified object into this MDkNNTree-Tree.
private void	leafEntryIDs(MkAppTreeNode<O,D,N> node, List<Integer> result) Determines the ids of the leaf entries stored in the specified subtree.
protected void	preInsert(MkAppEntry<D,N> entry) Performs necessary operations before inserting the specified entry.
List<DistanceResultPair<D>>	reverseKNNQuery(O object, int k) Performs a reverse k-nearest neighbor query for the given object ID.
List<String>	setParameters(List<String> args) Calls TreeIndex#setParameters and instantiates AbstractMTree.distanceFunction according to the value of parameter AbstractMTree.DISTANCE_FUNCTION_PARAM.

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

batchNN, createEmptyRoot, delete, distance, doKNNQuery, getDistanceFunction, getSortedEntries, getSortedEntries, insert, kNNQuery, postDelete, rangeQuery, setDatabase, toString

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

close, createHeader, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeFromFile, resetPageAccess

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, progress, verbose, warning

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.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription

Field Detail

NOLOG_ID

public static final OptionID NOLOG_ID

OptionID for NOLOG_PARAM

NOLOG_PARAM

private final Flag NOLOG_PARAM

Parameter for nolog

K_ID

public static final OptionID K_ID

OptionID for K_PARAM

K_PARAM

private final IntParameter K_PARAM

Parameter for k

P_ID

public static final OptionID P_ID

OptionID for P_PARAM

P_PARAM

private final IntParameter P_PARAM

Parameter for p

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

Creates a new MkCopTree.

Method Detail

insert

public void insert(O object)

Inserts the specified object into this MDkNNTree-Tree. This operation is not supported.

Parameters:

object - the object to be inserted

preInsert

protected void preInsert(MkAppEntry<D,N> entry)

Performs necessary operations before inserting the specified entry.

Specified by:

preInsert in class TreeIndex<O extends DatabaseObject,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

entry - the entry to be inserted

insert

public void insert(List<O> objects)

Inserts the specified objects into this MkApp-Tree.

Parameters:

objects - the object to be inserted

reverseKNNQuery

public List<DistanceResultPair<D>> reverseKNNQuery(O object,
                                                   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 MetricalIndex<O extends DatabaseObject,D extends NumberDistance<D,N>,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

object - the query object

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

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException

Description copied from class: AbstractMTree

Calls TreeIndex#setParameters and instantiates AbstractMTree.distanceFunction according to the value of parameter AbstractMTree.DISTANCE_FUNCTION_PARAM. The remaining parameters are passed to the AbstractMTree.distanceFunction.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D,N>,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

a list containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

initializeCapacities

protected void initializeCapacities(O object,
                                    boolean verbose)

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

Specified by:

initializeCapacities in class TreeIndex<O extends DatabaseObject,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

doReverseKNNQuery

private List<DistanceResultPair<D>> doReverseKNNQuery(int k,
                                                      Integer 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(List<Integer> ids,
                               Map<Integer,KNNList<D>> knnLists)

adjustApproximatedKNNDistances

private void adjustApproximatedKNNDistances(MkAppEntry<D,N> entry,
                                            Map<Integer,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,N> node,
                          List<Integer> 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,N> createNewLeafNode(int capacity)

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class TreeIndex<O extends DatabaseObject,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

protected MkAppTreeNode<O,D,N> createNewDirectoryNode(int capacity)

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class TreeIndex<O extends DatabaseObject,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

createNewLeafEntry

protected MkAppEntry<D,N> createNewLeafEntry(O object,
                                             D parentDistance)

Creates a new leaf entry representing the specified data object in the specified subtree.

Specified by:

createNewLeafEntry in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D,N>,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

object - the data object to be represented by the new entry

parentDistance - the distance from the object to the routing object of the parent node

Returns:

the newly created leaf entry

createNewDirectoryEntry

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

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D,N>,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

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,N> createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class TreeIndex<O extends DatabaseObject,MkAppTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkAppEntry<D extends NumberDistance<D,N>,N extends Number>>

Returns:

an entry representing the root node