de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees
Class AbstractMkTree<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      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,N,E>
                  de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,D,N,E>

Type Parameters:

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

D - the type of Distance used in the metrical index

N - the type of MetricalNode used in the metrical index

E - the type of MetricalEntry used in the metrical index

All Implemented Interfaces:

Index<O>, Parameterizable

Direct Known Subclasses:

MkMaxTree, MkTabTree

public abstract class AbstractMkTree<O extends DatabaseObject,D extends Distance<D>,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>
extends AbstractMTree<O,D,N,E>

Abstract class for all M-Tree variants supporting processing of reverse k-nearest neighbor queries by using the k-nn distances of the entries, where k is less than or equal to the specified parameter K_MAX_PARAM.

Author:

Elke Achtert

Field Summary

protected int	k_max Holds the value of parameter K_MAX_PARAM.
static OptionID	K_MAX_ID OptionID for K_MAX_PARAM.
IntParameter	K_MAX_PARAM Parameter specifying the maximal number k of reverse k nearest neighbors to be supported, must be an integer greater than 0.

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.logging.AbstractLoggable

debug, logger

Constructor Summary

AbstractMkTree(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

protected TreeIndexHeader	createHeader() Creates a header for this index structure which is an instance of TreeIndexHeader.
void	insert(List<O> objects) Inserts the specified objects into this M-Tree sequentially since a bulk load method is not implemented so far.
protected abstract void	kNNdistanceAdjustment(E entry, Map<Integer,KNNList<D>> knnLists) Performs a distance adjustment in the subtree of the specified root entry.

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

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

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

reverseKNNQuery

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

close, createNewDirectoryNode, createNewLeafNode, createRootEntry, getFileName, getLogicalPageAccess, getNode, getNode, getNodeClass, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeCapacities, initializeFromFile, preInsert, resetPageAccess

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.index.Index

insert

Field Detail

K_MAX_ID

public static final OptionID K_MAX_ID

OptionID for K_MAX_PARAM.

K_MAX_PARAM

public final IntParameter K_MAX_PARAM

Parameter specifying the maximal number k of reverse k nearest neighbors to be supported, must be an integer greater than 0.

Key: -mktree.kmax

k_max

protected int k_max

Holds the value of parameter K_MAX_PARAM.

Constructor Detail

AbstractMkTree

public AbstractMkTree(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

insert

public final void insert(List<O> objects)

Inserts the specified objects into this M-Tree sequentially since a bulk load method is not implemented so far.

Calls for each object AbstractMTree.insert(object, false). After insertion a batch knn query is performed and the knn distances are adjusted.

Parameters:

objects - the objects to be inserted

createHeader

protected TreeIndexHeader createHeader()

Description copied from class: TreeIndex

Creates a header for this index structure which is an instance of TreeIndexHeader. Subclasses may need to overwrite this method if they need a more specialized header.

Overrides:

createHeader in class TreeIndex<O extends DatabaseObject,N extends AbstractMTreeNode<O,D,N,E>,E extends MTreeEntry<D>>

Returns:

a new MkTreeHeader

kNNdistanceAdjustment

protected abstract void kNNdistanceAdjustment(E entry,
                                              Map<Integer,KNNList<D>> knnLists)

Performs a distance adjustment 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