de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktab
Class MkTabTree<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,MkTabTreeNode<O,D>,MkTabEntry<D>>
                      de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktab.MkTabTree<O,D>

All Implemented Interfaces:

Index<O>, Loggable, Parameterizable

public class MkTabTree<O extends DatabaseObject,D extends Distance<D>>
extends AbstractMTree<O,D,MkTabTreeNode<O,D>,MkTabEntry<D>>

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

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.

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

MkTabTree()
Creates a new MkNNTabTree.

Method Summary

private void	adjustKNNDistances(MkTabEntry<D> entry, Map<Integer,KNNList<D>> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
protected TreeIndexHeader	createHeader() Creates a header for this index structure.
protected MkTabEntry<D>	createNewDirectoryEntry(MkTabTreeNode<O,D> node, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkTabTreeNode<O,D>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MkTabEntry<D>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object in the specified subtree.
protected MkTabTreeNode<O,D>	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected MkTabEntry<D>	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNNQuery(int k, Integer q, MkTabEntry<D> node_entry, MkTabTreeNode<O,D> node, List<QueryResult<D>> result) Performs a k-nearest neighbor query in the specified subtree for the given query object and the given parameter k.
protected void	initCapacity(O object) Determines the maximum and minimum number of entries in a node.
private List<D>	initKnnDistanceList() Retuns a knn distance list with all distances set to null distance.
void	insert(List<O> objects) Inserts the specified objects into this MDkNNTree-Tree.
void	insert(O object) Inserts the specified object into this MDkNNTree-Tree.
private List<D>	knnDistances(Integer objectID) Returns the knn distance of the object with the specified id.
private List<D>	max(List<D> distances1, List<D> distances2) Returns an array that holds the maximum values of the both specified arrays in each index.
protected void	preInsert(MkTabEntry<D> entry) Performs necessary operations before inserting the specified entry.
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, 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.

Constructor Detail

MkTabTree

public MkTabTree()

Creates a new MkNNTabTree.

Method Detail

preInsert

protected void preInsert(MkTabEntry<D> entry)

Performs necessary operations before inserting the specified entry.

Specified by:

preInsert in class TreeIndex<O extends DatabaseObject,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

entry - the entry to be inserted

insert

public void insert(O object)

Inserts the specified object into this MDkNNTree-Tree. This operation is not supported. todo Provide insertion of single objects

Specified by:

insert in interface Index<O extends DatabaseObject>

Overrides:

insert in class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

object - the object to be inserted

insert

public void insert(List<O> objects)

Inserts the specified objects into this MDkNNTree-Tree.

Specified by:

insert in interface Index<O extends DatabaseObject>

Overrides:

insert in class AbstractMTree<O extends DatabaseObject,D extends Distance<D>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<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>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<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

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>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<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[])

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,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Returns:

a header for this index structure

initCapacity

protected void initCapacity(O object)

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

Parameters:

object - a object that is stored in the tree

doReverseKNNQuery

private void doReverseKNNQuery(int k,
                               Integer q,
                               MkTabEntry<D> node_entry,
                               MkTabTreeNode<O,D> node,
                               List<QueryResult<D>> result)

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

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

knnDistances

private List<D> knnDistances(Integer objectID)

Returns the knn distance of the object with the specified id.

Parameters:

objectID - the id of the query object

Returns:

the knn distance of the object with the specified id

adjustKNNDistances

private void adjustKNNDistances(MkTabEntry<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

max

private List<D> max(List<D> distances1,
                    List<D> 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 List<D> initKnnDistanceList()

Retuns a knn distance list with all distances set to null distance.

Returns:

a knn distance list with all distances set to null distance

createNewLeafNode

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

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class TreeIndex<O extends DatabaseObject,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

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

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class TreeIndex<O extends DatabaseObject,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

createNewLeafEntry

protected MkTabEntry<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>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<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 MkTabEntry<D> createNewDirectoryEntry(MkTabTreeNode<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>,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<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 MkTabEntry<D> createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class TreeIndex<O extends DatabaseObject,MkTabTreeNode<O extends DatabaseObject,D extends Distance<D>>,MkTabEntry<D extends Distance<D>>>

Returns:

an entry representing the root node