|
|
|||||||||||||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
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>
O
- the type of DatabaseObject to be stored in the metrical indexD
- the type of NumberDistance used in the metrical indexN
- the type of Number used in the NumberDistancepublic class MkAppTree<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>
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 | |
---|---|
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 |
---|
public static final OptionID NOLOG_ID
NOLOG_PARAM
private final Flag NOLOG_PARAM
public static final OptionID K_ID
K_PARAM
private final IntParameter K_PARAM
public static final OptionID P_ID
P_PARAM
private final IntParameter P_PARAM
private int k_max
private int p
private boolean log
Constructor Detail |
---|
public MkAppTree()
Method Detail |
---|
public void insert(O object)
object
- the object to be insertedprotected void preInsert(MkAppEntry<D,N> entry)
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>>
entry
- the entry to be insertedpublic void insert(List<O> objects)
objects
- the object to be insertedpublic List<DistanceResultPair<D>> reverseKNNQuery(O object, int k)
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>>
object
- the query objectk
- the number of nearest neighbors to be returned
public int getK_max()
public List<String> setParameters(List<String> args) throws ParameterException
AbstractMTree
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
.
setParameters
in interface Parameterizable
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>>
args
- parameters to set the attributes accordingly to
ParameterException
- in case of wrong parameter-settingprotected void initializeCapacities(O object, boolean verbose)
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>>
object
- an object that will be stored in the indexverbose
- flag to allow verbose messagesprivate List<DistanceResultPair<D>> doReverseKNNQuery(int k, Integer q)
k
- the parameter k of the rknn queryq
- the id of the query object
private List<D> getMeanKNNList(List<Integer> ids, Map<Integer,KNNList<D>> knnLists)
private void adjustApproximatedKNNDistances(MkAppEntry<D,N> entry, Map<Integer,KNNList<D>> knnLists)
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entryprivate void leafEntryIDs(MkAppTreeNode<O,D,N> node, List<Integer> result)
node
- the root of the subtreeresult
- the result list containing the ids of the leaf entries stored
in the specified subtreeprivate PolynomialApproximation approximateKnnDistances(List<D> knnDistances)
knnDistances
- the knn-distances of the leaf entry
protected MkAppTreeNode<O,D,N> createNewLeafNode(int capacity)
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>>
capacity
- the capacity of the new node
protected MkAppTreeNode<O,D,N> createNewDirectoryNode(int capacity)
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>>
capacity
- the capacity of the new node
protected MkAppEntry<D,N> createNewLeafEntry(O object, D parentDistance)
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>>
object
- the data object to be represented by the new entryparentDistance
- the distance from the object to the routing object of
the parent node
protected MkAppEntry<D,N> createNewDirectoryEntry(MkAppTreeNode<O,D,N> node, Integer routingObjectID, D parentDistance)
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>>
node
- the node to be represented by the new entryroutingObjectID
- the id of the routing object of the nodeparentDistance
- the distance from the routing object of the node to
the routing object of the parent node
protected MkAppEntry<D,N> createRootEntry()
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>>
|
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |