de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mkmax
Class MkMaxTree<O extends DatabaseObject,D extends Distance<D>>

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,MkMaxTreeNode<O,D>,MkMaxEntry<D>>
                      de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mkmax.MkMaxTree<O,D>

All Implemented Interfaces:

Index<O>, Loggable, Parameterizable

public class MkMaxTree<O extends DatabaseObject,D extends Distance<D>>
extends AbstractMTree<O,D,MkMaxTreeNode<O,D>,MkMaxEntry<D>>

MkNNTree is a metrical index structure based on the concepts of the M-Tree supporting efficient processing of reverse k nearest neighbor queries. The k-nn distance is stored in each entry of a node.

Author:

Elke Achtert

Field Summary

static String	K_D Description for parameter k.
(package private) int	k_max Parameter k.
static String	K_P Parameter k.
private RkNNStatistic	rkNNStatistics Provides some statistics about performed reverse knn-queries.

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

DEFAULT_DISTANCE_FUNCTION, DISTANCE_FUNCTION_D, DISTANCE_FUNCTION_P

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

CACHE_SIZE_D, CACHE_SIZE_P, cacheSize, DEFAULT_CACHE_SIZE, DEFAULT_PAGE_SIZE, dirCapacity, dirMinimum, file, FILE_NAME_D, FILE_NAME_P, initialized, leafCapacity, leafMinimum, PAGE_SIZE_D, PAGE_SIZE_P, 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

Constructor Summary

MkMaxTree()
Creates a new MkMaxTree.

Method Summary

private void	adjustKNNDistance(MkMaxEntry<D> entry, Map<Integer,KNNList<D>> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
void	clearRkNNStatistics() Clears the values of the statistic for performed rknn queries
protected TreeIndexHeader	createHeader() Creates a header for this index structure.
protected MkMaxEntry<D>	createNewDirectoryEntry(MkMaxTreeNode<O,D> node, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkMaxTreeNode<O,D>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MkMaxEntry<D>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object in the specified subtree.
protected MkMaxTreeNode<O,D>	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected MkMaxEntry<D>	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNNQuery(Integer q, MkMaxEntry<D> node_entry, MkMaxTreeNode<O,D> node, List<QueryResult<D>> result) Performs a k-nearest neighbor query in the specified subtree for the given query object.
RkNNStatistic	getRkNNStatistics() Returns the statistic for performed rknn queries.
protected void	initCapacity(int pageSize) Determines the maximum and minimum number of entries in a node.
void	insert(List<O> objects) Inserts the specified objects into this MkMaxTree-Tree.
protected void	preInsert(MkMaxEntry<D> entry) Performs necessary operations before inserting the specified entry.
private void	preInsert(MkMaxEntry<D> q, MkMaxEntry<D> nodeEntry, KNNList<D> knns_q) Adapts the knn distances before insertion of entry q.
List<QueryResult<D>>	reverseKNNQuery(O object, int k) Performs a reverse k-nearest neighbor query for the given object ID.
String[]	setParameters(String[] args) Sets the attributes of the class accordingly to the given parameters.

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

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

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

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

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

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

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

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, 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, getParameters, getPossibleOptions, inlineDescription

Field Detail

K_P

public static final String K_P

Parameter k.

See Also:

Constant Field Values

K_D

public static final String K_D

Description for parameter k.

See Also:

Constant Field Values

k_max

int k_max

Parameter k.

rkNNStatistics

private RkNNStatistic rkNNStatistics

Provides some statistics about performed reverse knn-queries.

Constructor Detail

MkMaxTree

public MkMaxTree()

Creates a new MkMaxTree.

Method Detail

preInsert

protected void preInsert(MkMaxEntry<D> entry)

Performs necessary operations before inserting the specified entry.

Specified by:

preInsert in class TreeIndex<O extends DatabaseObject,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

entry - the entry to be inserted

insert

public void insert(List<O> objects)

Inserts the specified objects into this MkMaxTree-Tree.

Specified by:

insert in interface Index<O extends DatabaseObject>

Overrides:

insert in class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

objects - the object to be inserted

reverseKNNQuery

public List<QueryResult<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.

Overrides:

reverseKNNQuery in class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

object - the query object

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

getRkNNStatistics

public RkNNStatistic getRkNNStatistics()

Returns the statistic for performed rknn queries.

Returns:

the statistic for performed rknn queries

clearRkNNStatistics

public void clearRkNNStatistics()

Clears the values of the statistic for performed rknn queries

createHeader

protected TreeIndexHeader createHeader()

Creates a header for this index structure. Subclasses may need to overwrite this method.

Overrides:

createHeader in class TreeIndex<O extends DatabaseObject,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

a header for this index structure

doReverseKNNQuery

private void doReverseKNNQuery(Integer q,
                               MkMaxEntry<D> node_entry,
                               MkMaxTreeNode<O,D> node,
                               List<QueryResult<D>> result)

Performs a k-nearest neighbor query in the specified subtree for the given query object.

Parameters:

q - the id of the query object

node_entry - the entry representing the node

node - the node of the subtree on which the query is performed

result - the list for the query result

preInsert

private void preInsert(MkMaxEntry<D> q,
                       MkMaxEntry<D> nodeEntry,
                       KNNList<D> knns_q)

Adapts the knn distances before insertion of entry q.

Parameters:

q - the entry to be inserted

nodeEntry - the entry representing the root of thge current subtree

knns_q - the knns of q

adjustKNNDistance

private void adjustKNNDistance(MkMaxEntry<D> 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

initCapacity

protected void initCapacity(int pageSize)

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

Parameters:

pageSize - the size of a page in Bytes

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Description copied from interface: Parameterizable

Sets the attributes of the class accordingly to the given parameters. Returns a new String array containing those entries of the given array that are neither expected nor used by this Parameterizable.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

createNewLeafNode

protected MkMaxTreeNode<O,D> createNewLeafNode(int capacity)

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class TreeIndex<O extends DatabaseObject,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

protected MkMaxTreeNode<O,D> createNewDirectoryNode(int capacity)

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class TreeIndex<O extends DatabaseObject,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

createNewLeafEntry

protected MkMaxEntry<D> 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 Distance<D>,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

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 MkMaxEntry<D> createNewDirectoryEntry(MkMaxTreeNode<O,D> 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 Distance<D>,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<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 MkMaxEntry<D> createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class TreeIndex<O extends DatabaseObject,MkMaxTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkMaxEntry<D extends Distance<D>>>

Returns:

an entry representing the root node