O
- Object typeD
- Distance typepublic class MkCoPTree<O,D extends NumberDistance<D,?>> extends AbstractMkTree<O,D,MkCoPTreeNode<O,D>,MkCoPEntry<D>>
Modifier and Type | Field and Description |
---|---|
(package private) int |
k_max
Parameter k.
|
private double[] |
log_k
The values of log(1),..
|
private static Logging |
logger
The logger for this class.
|
private QueryStatistic |
rkNNStatistics
Provides some statistics about performed reverse knn-queries.
|
distanceFunction, distanceQuery, extraIntegrityChecks
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor and Description |
---|
MkCoPTree(PageFile<MkCoPTreeNode<O,D>> pagefile,
DistanceQuery<O,D> distanceQuery,
DistanceFunction<O,D> distanceFunction,
int k_max)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
private void |
adjustApproximatedKNNDistances(MkCoPEntry<D> entry,
Map<DBID,KNNList<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.
|
private void |
approximateKnnDistances(MkCoPLeafEntry<D> entry,
KNNList<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> |
createNewDirectoryEntry(MkCoPTreeNode<O,D> node,
DBID routingObjectID,
D parentDistance)
Creates a new directory entry representing the specified node.
|
protected MkCoPTreeNode<O,D> |
createNewDirectoryNode()
Creates a new directory node with the specified capacity.
|
protected MkCoPTreeNode<O,D> |
createNewLeafNode()
Creates a new leaf node with the specified capacity.
|
protected MkCoPEntry<D> |
createRootEntry()
Creates an entry representing the root node.
|
private void |
doReverseKNNQuery(int k,
DBIDRef q,
List<DistanceResultPair<D>> result,
ModifiableDBIDs candidates)
Performs a reverse knn query.
|
int |
getK_max()
Returns the value of the k_max parameter.
|
protected Logging |
getLogger()
Get the (STATIC) logger for this class.
|
QueryStatistic |
getRkNNStatistics()
Returns the statistic for performed rknn queries.
|
protected void |
initializeCapacities(MkCoPEntry<D> exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
void |
insert(MkCoPEntry<D> entry,
boolean withPreInsert)
Inserts the specified object into this M-Tree.
|
void |
insertAll(List<MkCoPEntry<D>> entries)
Bulk insert.
|
private double |
optimize(int k0,
int kmax,
double sumx,
double sumx2,
double xp,
double yp,
double sumxy,
double sumy) |
protected void |
preInsert(MkCoPEntry<D> entry)
Performs necessary operations before inserting the specified entry.
|
List<DistanceResultPair<D>> |
reverseKNNQuery(DBIDRef id,
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) |
batchNN, createEmptyRoot, distance, distance, doKNNQuery, getDistanceFactory, getDistanceFunction, getDistanceQuery, getHeight, getLeaves, getSortedEntries, getSortedEntries, toString
createHeader, deleteNode, getFile, getNode, getNode, getPageFileStatistics, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging logger
int k_max
private double[] log_k
private QueryStatistic rkNNStatistics
public MkCoPTree(PageFile<MkCoPTreeNode<O,D>> pagefile, DistanceQuery<O,D> distanceQuery, DistanceFunction<O,D> distanceFunction, int k_max)
pagefile
- Page filedistanceQuery
- Distance querydistanceFunction
- Distance functionk_max
- Maximum value of k supportedprotected void preInsert(MkCoPEntry<D> entry)
IndexTree
preInsert
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
entry
- the entry to be insertedUnsupportedOperationException
- since this operation is not supportedpublic void insert(MkCoPEntry<D> entry, boolean withPreInsert)
AbstractMTree
insert
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
entry
- the entry to be insertedwithPreInsert
- if this flag is true, the preInsert method will be
called before inserting the objectUnsupportedOperationException
- since this operation is not supportedpublic void insertAll(List<MkCoPEntry<D>> entries)
AbstractMTree
insertAll
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k)
reverseKNNQuery
in class AbstractMkTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
id
- the query object idk
- the number of nearest neighbors to be returnedpublic QueryStatistic getRkNNStatistics()
public void clearRkNNStatistics()
public int getK_max()
protected void initializeCapacities(MkCoPEntry<D> exampleLeaf)
initializeCapacities
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
exampleLeaf
- an object that will be stored in the indexprivate void doReverseKNNQuery(int k, DBIDRef q, List<DistanceResultPair<D>> result, ModifiableDBIDs 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 void adjustApproximatedKNNDistances(MkCoPEntry<D> entry, Map<DBID,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> entry, KNNList<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> createNewLeafNode()
createNewLeafNode
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
protected MkCoPTreeNode<O,D> createNewDirectoryNode()
createNewDirectoryNode
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
protected MkCoPEntry<D> createNewDirectoryEntry(MkCoPTreeNode<O,D> node, DBID routingObjectID, D parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
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 nodeprotected MkCoPEntry<D> createRootEntry()
createRootEntry
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry<D extends NumberDistance<D,?>>>