O
- Object typeD
- Distance typepublic class MkCoPTree<O,D extends NumberDistance<D,?>> extends AbstractMkTree<O,D,MkCoPTreeNode<O,D>,MkCoPEntry,MkTreeSettings<O,D,MkCoPTreeNode<O,D>,MkCoPEntry>>
AbstractMTree.Statistics
Modifier and Type | Field and Description |
---|---|
private static Logging |
LOG
The logger for this class.
|
private double[] |
log_k
The values of log(1),..
|
knnq
EXTRA_INTEGRITY_CHECKS, settings, statistics
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
Constructor and Description |
---|
MkCoPTree(Relation<O> relation,
PageFile<MkCoPTreeNode<O,D>> pagefile,
MkTreeSettings<O,D,MkCoPTreeNode<O,D>,MkCoPEntry> settings)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
private void |
adjustApproximatedKNNDistances(MkCoPEntry entry,
Map<DBID,KNNList<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.
|
private void |
approximateKnnDistances(MkCoPLeafEntry 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) |
protected MkCoPEntry |
createNewDirectoryEntry(MkCoPTreeNode<O,D> node,
DBID routingObjectID,
double 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 |
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.
|
protected void |
initializeCapacities(MkCoPEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.
|
void |
insert(MkCoPEntry entry,
boolean withPreInsert)
Inserts the specified object into this M-Tree.
|
void |
insertAll(List<MkCoPEntry> 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 entry)
Performs necessary operations before inserting the specified entry.
|
DistanceDBIDList<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, distance
createEmptyRoot, distance, getDistanceFactory, getDistanceFunction, getHeight, getLeaves, getSortedEntries, logStatistics, toString
createHeader, deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
private static final Logging LOG
private double[] log_k
public MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O,D>> pagefile, MkTreeSettings<O,D,MkCoPTreeNode<O,D>,MkCoPEntry> settings)
relation
- Relation to indexpagefile
- Page filesettings
- Tree settingsprotected void preInsert(MkCoPEntry entry)
IndexTree
preInsert
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>
entry
- the entry to be insertedUnsupportedOperationException
- since this operation is not supportedpublic void insert(MkCoPEntry entry, boolean withPreInsert)
AbstractMTree
insert
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>>
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> entries)
AbstractMTree
insertAll
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>>
entries
- Entries to insertpublic DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k)
reverseKNNQuery
in class AbstractMkTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>>
id
- the query object idk
- the number of nearest neighbors to be returnedpublic int getK_max()
protected void initializeCapacities(MkCoPEntry exampleLeaf)
initializeCapacities
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>
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 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 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>
protected MkCoPTreeNode<O,D> createNewDirectoryNode()
createNewDirectoryNode
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>
protected MkCoPEntry createNewDirectoryEntry(MkCoPTreeNode<O,D> node, DBID routingObjectID, double parentDistance)
createNewDirectoryEntry
in class AbstractMTree<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry,MkTreeSettings<O,D extends NumberDistance<D,?>,MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>>
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 createRootEntry()
createRootEntry
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>
protected Logging getLogger()
IndexTree
getLogger
in class IndexTree<MkCoPTreeNode<O,D extends NumberDistance<D,?>>,MkCoPEntry>