de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop

Class MkCoPTree<O>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree<O,N,E>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop.MkCoPTree<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, Result

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 de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

AbstractMTree.Statistics

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG The logger for this class.
private double[]	log_k The values of log(1),..

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree

knnq

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

EXTRA_INTEGRITY_CHECKS, settings, statistics

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O>> pagefile, MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry> settings) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private void	adjustApproximatedKNNDistances(MkCoPEntry entry, 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 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> 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	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.
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 de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree

batchNN, distance

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree

createEmptyRoot, distance, getDistanceFunction, getHeight, getLeaves, getSortedEntries, logStatistics, toString

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

createHeader, deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeFromFile, isRoot, postDelete, writeNode

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

getLongName, getShortName

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 index

pagefile - Page file

settings - 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 class IndexTree<MkCoPTreeNode<O>,MkCoPEntry>

Parameters:

entry - the entry to be inserted

Throws:

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 class AbstractMTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>

Parameters:

entry - the entry to be inserted

withPreInsert - if this flag is true, the preInsert method will be called before inserting the object

Throws:

UnsupportedOperationException - since this operation is not supported

insertAll

public void insertAll(List<MkCoPEntry> entries)

Description copied from class: AbstractMTree

Bulk insert.

Overrides:

insertAll in class AbstractMTree<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 class AbstractMkTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

getK_max

public int getK_max()

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 class IndexTree<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 query

q - the id of the query object

result - 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,
                                  Map<DBID,KNNList> knnLists)

Adjusts the knn distance in the subtree of the specified root entry.

Parameters:

entry - the root entry of the current subtree

knnLists - 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)

approximateUpperHull_PAPER

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)

approximateUpperHull_OLD

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)

createNewLeafNode

protected MkCoPTreeNode<O> createNewLeafNode()

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<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 class IndexTree<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 class AbstractMTree<O,MkCoPTreeNode<O>,MkCoPEntry,MkTreeSettings<O,MkCoPTreeNode<O>,MkCoPEntry>>

Parameters:

node - the node to be represented by the new entry

routingObjectID - the id of the routing object of the node

parentDistance - 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 class IndexTree<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 class IndexTree<MkCoPTreeNode<O>,MkCoPEntry>

Returns:

the static logger