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 static Logging |
LOG
The logger for this class.
|
private double[] |
log_k
The values of log(1),..
|
private QueryStatistic |
rkNNStatistics
Provides some statistics about performed reverse knn-queries.
|
knnq
distanceFunction, distanceQuery, EXTRA_INTEGRITY_CHECKS
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,KNNResult<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.
|
private void |
approximateKnnDistances(MkCoPLeafEntry<D> entry,
KNNResult<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,
GenericDistanceDBIDList<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.
|
DistanceDBIDResult<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, 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 LOG
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,?>>>
entries
- Entries to insertpublic DistanceDBIDResult<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, GenericDistanceDBIDList<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,KNNResult<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, KNNResult<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,?>>>