|
|
|||||||||||||||||||||
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.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,MkCoPTreeNode<O,D,N>,MkCoPEntry<D,N>> de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop.MkCoPTree<O,D,N>
O
- Object typeD
- Distance typeN
- Number typepublic class MkCoPTree<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>
MkCopTree 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 |
(package private) int |
k_max
Parameter k. |
private IntParameter |
K_PARAM
Parameter for k |
private double[] |
log_k
The values of log(1),.. |
private QueryStatistic |
rkNNStatistics
Provides some statistics about performed reverse knn-queries. |
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 | |
---|---|
MkCoPTree(Parameterization config)
Constructor, adhering to Parameterizable |
Method Summary | |
---|---|
private void |
adjustApproximatedKNNDistances(MkCoPEntry<D,N> entry,
Map<Integer,KNNList<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry. |
private void |
approximateKnnDistances(MkCoPLeafEntry<D,N> entry,
List<D> knnDistances)
Computes logarithmic skew (fractal dimension ie. m) and in kappx[0] and kappx[1] the non-logarithmic values of the approximated first and last nearest neighbor distances |
private ApproximationLine |
approximateLowerHull(ConvexHull convexHull,
double[] log_k,
double sum_log_k,
double sum_log_k2,
double[] log_kDist,
double sum_log_kDist,
double sum_log_k_kDist)
Approximates the lower hull. |
private ApproximationLine |
approximateUpperHull_OLD(ConvexHull convexHull,
double[] log_k,
double sum_log_k,
double sum_log_k2,
double[] log_kDist,
double sum_log_kDist,
double sum_log_k_kDist)
|
private ApproximationLine |
approximateUpperHull_PAPER(ConvexHull convexHull,
double[] log_k,
double sum_log_k,
double sum_log_k2,
double[] log_kDist,
double sum_log_kDist,
double sum_log_k_kDist)
|
private ApproximationLine |
approximateUpperHull(ConvexHull convexHull,
double[] log_k,
double[] log_kDist)
|
void |
clearRkNNStatistics()
Clears the values of the statistic for performed rknn queries |
protected MkCoPEntry<D,N> |
createNewDirectoryEntry(MkCoPTreeNode<O,D,N> node,
Integer routingObjectID,
D parentDistance)
Creates a new directory entry representing the specified node. |
protected MkCoPTreeNode<O,D,N> |
createNewDirectoryNode(int capacity)
Creates a new directory node with the specified capacity. |
protected MkCoPEntry<D,N> |
createNewLeafEntry(O object,
D parentDistance)
Creates a new leaf entry representing the specified data object in the specified subtree. |
protected MkCoPTreeNode<O,D,N> |
createNewLeafNode(int capacity)
Creates a new leaf node with the specified capacity. |
protected MkCoPEntry<D,N> |
createRootEntry()
Creates an entry representing the root node. |
private void |
doReverseKNNQuery(int k,
Integer q,
List<DistanceResultPair<D>> result,
List<Integer> candidates)
Performs a reverse knn query. |
int |
getK_max()
Returns the value of the k_max parameter. |
private List<D> |
getKNNList(Integer id,
Map<Integer,KNNList<D>> knnLists)
|
protected Class<MkCoPTreeNode<O,D,N>> |
getNodeClass()
Return the node base class. |
QueryStatistic |
getRkNNStatistics()
Returns the statistic for performed rknn queries. |
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 MDkNNTree-Tree. |
void |
insert(O object)
Inserts the specified object into this MDkNNTree-Tree. |
private double |
optimize(int k0,
int kmax,
double sumx,
double sumx2,
double xp,
double yp,
double sumxy,
double sumy)
|
protected void |
preInsert(MkCoPEntry<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. |
private double |
ssqerr(int k0,
int kmax,
double[] logk,
double[] log_kDist,
double m,
double t)
|
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, rangeQuery, setDatabase, toString |
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex |
---|
close, createHeader, getFileName, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeFromFile, 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 |
Field Detail |
---|
public static final OptionID K_ID
K_PARAM
private final IntParameter K_PARAM
int k_max
private double[] log_k
private QueryStatistic rkNNStatistics
Constructor Detail |
---|
public MkCoPTree(Parameterization config)
Parameterizable
config
- ParameterizationMethod Detail |
---|
public void insert(O object)
object
- the object to be insertedprotected void preInsert(MkCoPEntry<D,N> entry)
preInsert
in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<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>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
object
- the query objectk
- the number of nearest neighbors to be returned
public QueryStatistic getRkNNStatistics()
public void clearRkNNStatistics()
public int getK_max()
protected void initializeCapacities(O object, boolean verbose)
initializeCapacities
in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
object
- an object that will be stored in the indexverbose
- flag to allow verbose messagesprivate void doReverseKNNQuery(int k, Integer q, List<DistanceResultPair<D>> result, List<Integer> candidates)
k
- the parameter k of the rknn queryq
- the id of the query objectresult
- holds the true results (they need not to be refined)candidates
- holds possible candidates for the result (they need a
refinement)private List<D> getKNNList(Integer id, Map<Integer,KNNList<D>> knnLists)
private void adjustApproximatedKNNDistances(MkCoPEntry<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 double ssqerr(int k0, int kmax, double[] logk, double[] log_kDist, double m, double t)
private double optimize(int k0, int kmax, double sumx, double sumx2, double xp, double yp, double sumxy, double sumy)
private void approximateKnnDistances(MkCoPLeafEntry<D,N> entry, List<D> knnDistances)
knnDistances
- TODO: Spezialbehandlung fuer identische Punkte in DB
(insbes. Distanz 0)private ApproximationLine approximateLowerHull(ConvexHull convexHull, double[] log_k, double sum_log_k, double sum_log_k2, double[] log_kDist, double sum_log_kDist, double sum_log_k_kDist)
convexHull
- log_kDist
- sum_log_kDist
- sum_log_k_kDist
- private ApproximationLine approximateUpperHull(ConvexHull convexHull, double[] log_k, double[] log_kDist)
private ApproximationLine approximateUpperHull_PAPER(ConvexHull convexHull, double[] log_k, double sum_log_k, double sum_log_k2, double[] log_kDist, double sum_log_kDist, double sum_log_k_kDist)
private ApproximationLine approximateUpperHull_OLD(ConvexHull convexHull, double[] log_k, double sum_log_k, double sum_log_k2, double[] log_kDist, double sum_log_kDist, double sum_log_k_kDist)
protected MkCoPTreeNode<O,D,N> createNewLeafNode(int capacity)
createNewLeafNode
in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
capacity
- the capacity of the new node
protected MkCoPTreeNode<O,D,N> createNewDirectoryNode(int capacity)
createNewDirectoryNode
in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
capacity
- the capacity of the new node
protected MkCoPEntry<D,N> createNewLeafEntry(O object, D parentDistance)
createNewLeafEntry
in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D,N>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<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 MkCoPEntry<D,N> createNewDirectoryEntry(MkCoPTreeNode<O,D,N> node, Integer routingObjectID, D parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D,N>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<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 MkCoPEntry<D,N> createRootEntry()
createRootEntry
in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
protected Class<MkCoPTreeNode<O,D,N>> getNodeClass()
getNodeClass
in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
|
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |