Class MkCoPTree<O>
- java.lang.Object
-
- elki.index.tree.IndexTree<N,E>
-
- elki.index.tree.metrical.MetricalIndexTree<O,N,E>
-
- elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>
-
- elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>
-
- elki.index.tree.metrical.mtreevariants.mktrees.mkcop.MkCoPTree<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Index
- Direct Known Subclasses:
MkCoPTreeIndex
public abstract class MkCoPTree<O> extends AbstractMkTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>
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.- Since:
- 0.2
- Author:
- Elke Achtert
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree
AbstractMTree.Statistics
-
-
Field Summary
Fields Modifier and Type Field Description private static Logging
LOG
The logger for this class.private double[]
log_k
The values of log(1),..-
Fields inherited from class elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree
knnq
-
Fields inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree
settings, statistics
-
Fields inherited from class elki.index.tree.IndexTree
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
-
-
Constructor Summary
Constructors Constructor Description MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O>> pagefile, MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry> settings)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
adjustApproximatedKNNDistances(MkCoPEntry entry, java.util.Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.private void
approximateKnnDistances(MkCoPLeafEntry entry, KNNList 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 distancesprivate 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(ConvexHull convexHull, double[] log_k, double[] log_kDist)
private ApproximationLine
approximateUpperHullOld(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
approximateUpperHullPaper(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 MkCoPEntry
createNewDirectoryEntry(MkCoPTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.protected MkCoPTreeNode<O>
createNewDirectoryNode()
Creates a new directory node with the specified capacity.protected MkCoPTreeNode<O>
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, ModifiableDoubleDBIDList result, ModifiableDBIDs candidates)
Performs a reverse knn query.int
getKmax()
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(java.util.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.DoubleDBIDList
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)
-
Methods inherited from class elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree
batchNN, distance
-
Methods inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree
createEmptyRoot, distance, doExtraIntegrityChecks, getDistance, getHeight, getLeaves, getSortedEntries, logStatistics, toString
-
Methods inherited from class elki.index.tree.IndexTree
createHeader, deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
log_k
private double[] log_k
The values of log(1),..,log(k_max)
-
-
Constructor Detail
-
MkCoPTree
public MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O>> pagefile, MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry> settings)
Constructor.- Parameters:
relation
- Relation to indexpagefile
- Page filesettings
- Tree settings
-
-
Method Detail
-
preInsert
protected void preInsert(MkCoPEntry entry)
Description copied from class:IndexTree
Performs necessary operations before inserting the specified entry.- Overrides:
preInsert
in classIndexTree<MkCoPTreeNode<O>,MkCoPEntry>
- Parameters:
entry
- the entry to be inserted- Throws:
java.lang.UnsupportedOperationException
- since this operation is not supported
-
insert
public void insert(MkCoPEntry entry, boolean withPreInsert)
Description copied from class:AbstractMTree
Inserts the specified object into this M-Tree.- Overrides:
insert
in classAbstractMTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>
- Parameters:
entry
- the entry to be insertedwithPreInsert
- if this flag is true, the preInsert method will be called before inserting the object- Throws:
java.lang.UnsupportedOperationException
- since this operation is not supported
-
insertAll
public void insertAll(java.util.List<MkCoPEntry> entries)
Description copied from class:AbstractMTree
Bulk insert.- Overrides:
insertAll
in classAbstractMTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>
- Parameters:
entries
- Entries to insert
-
reverseKNNQuery
public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k)
Performs a reverse k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.- Specified by:
reverseKNNQuery
in classAbstractMkTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>
- Parameters:
id
- the query object idk
- the number of nearest neighbors to be returned- Returns:
- a List of the query results
-
getKmax
public int getKmax()
Returns the value of the k_max parameter.- Returns:
- the value of the k_max parameter
-
initializeCapacities
protected void initializeCapacities(MkCoPEntry exampleLeaf)
Determines the maximum and minimum number of entries in a node.- Specified by:
initializeCapacities
in classIndexTree<MkCoPTreeNode<O>,MkCoPEntry>
- Parameters:
exampleLeaf
- an object that will be stored in the index
-
doReverseKNNQuery
private void doReverseKNNQuery(int k, DBIDRef q, ModifiableDoubleDBIDList result, ModifiableDBIDs candidates)
Performs a reverse knn query.- Parameters:
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)
-
adjustApproximatedKNNDistances
private void adjustApproximatedKNNDistances(MkCoPEntry entry, java.util.Map<DBID,KNNList> knnLists)
Adjusts the knn distance in the subtree of the specified root entry.- Parameters:
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entry
-
ssqerr
private double ssqerr(int k0, int kmax, double[] logk, double[] log_kDist, double m, double t)
-
optimize
private double optimize(int k0, int kmax, double sumx, double sumx2, double xp, double yp, double sumxy, double sumy)
-
approximateKnnDistances
private void approximateKnnDistances(MkCoPLeafEntry entry, KNNList 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- Parameters:
knnDistances
- TODO: Spezialbehandlung fuer identische Punkte in DB (insbes. Distanz 0)
-
approximateLowerHull
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.- Parameters:
convexHull
-log_kDist
-sum_log_kDist
-sum_log_k_kDist
-
-
approximateUpperHull
private ApproximationLine approximateUpperHull(ConvexHull convexHull, double[] log_k, double[] log_kDist)
-
approximateUpperHullPaper
private ApproximationLine approximateUpperHullPaper(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)
-
approximateUpperHullOld
private ApproximationLine approximateUpperHullOld(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)
-
createNewLeafNode
protected MkCoPTreeNode<O> createNewLeafNode()
Creates a new leaf node with the specified capacity.- Specified by:
createNewLeafNode
in classIndexTree<MkCoPTreeNode<O>,MkCoPEntry>
- Returns:
- a new leaf node
-
createNewDirectoryNode
protected MkCoPTreeNode<O> createNewDirectoryNode()
Creates a new directory node with the specified capacity.- Specified by:
createNewDirectoryNode
in classIndexTree<MkCoPTreeNode<O>,MkCoPEntry>
- Returns:
- a new directory node
-
createNewDirectoryEntry
protected MkCoPEntry createNewDirectoryEntry(MkCoPTreeNode<O> node, DBID routingObjectID, double parentDistance)
Creates a new directory entry representing the specified node.- Specified by:
createNewDirectoryEntry
in classAbstractMTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>
- Parameters:
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- Returns:
- the newly created directory entry
-
createRootEntry
protected MkCoPEntry createRootEntry()
Creates an entry representing the root node.- Specified by:
createRootEntry
in classIndexTree<MkCoPTreeNode<O>,MkCoPEntry>
- Returns:
- an entry representing the root node
-
getLogger
protected Logging getLogger()
Description copied from class:IndexTree
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classIndexTree<MkCoPTreeNode<O>,MkCoPEntry>
- Returns:
- the static logger
-
-