de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mkcop
Class MkCoPTree<O extends DatabaseObject,D extends NumberDistance<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndex<O,D,N,E>
                  de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,MkCoPTreeNode<O,D>,MkCoPEntry<D>>
                      de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mkcop.MkCoPTree<O,D>

All Implemented Interfaces:

Index<O>, Loggable, Parameterizable

public class MkCoPTree<O extends DatabaseObject,D extends NumberDistance<D>>
extends AbstractMTree<O,D,MkCoPTreeNode<O,D>,MkCoPEntry<D>>

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.

Author:

Elke Achtert

Field Summary

static String	K_D Description for parameter k.
(package private) int	k_max Parameter k.
static String	K_P Parameter k.
private double[]	log_k The values of log(1),..
private RkNNStatistic	rkNNStatistics Provides some statistics about performed reverse knn-queries.

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

DEFAULT_DISTANCE_FUNCTION, DISTANCE_FUNCTION_D, DISTANCE_FUNCTION_P

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

CACHE_SIZE_D, CACHE_SIZE_P, cacheSize, DEFAULT_CACHE_SIZE, DEFAULT_PAGE_SIZE, dirCapacity, dirMinimum, file, FILE_NAME_D, FILE_NAME_P, initialized, leafCapacity, leafMinimum, PAGE_SIZE_D, PAGE_SIZE_P, pageSize

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug

Constructor Summary

MkCoPTree()
Creates a new MkCopTree.

Method Summary

private void	adjustApproximatedKNNDistances(MkCoPEntry<D> entry, Map<Integer,KNNList<D>> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
private void	approximateKnnDistances(MkCoPLeafEntry<D> entry, List<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, Integer routingObjectID, D parentDistance) Creates a new directory entry representing the specified node.
protected MkCoPTreeNode<O,D>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected MkCoPEntry<D>	createNewLeafEntry(O object, D parentDistance) Creates a new leaf entry representing the specified data object in the specified subtree.
protected MkCoPTreeNode<O,D>	createNewLeafNode(int capacity) 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, Integer q, List<QueryResult<D>> result, List<Integer> candidates) Performs a reverse knn query.
int	getK_max() Returns the value of the k_max parameter.
private List<D>	getKNNList(Integer id, Map<Integer,KNNList<D>> knnLists)
RkNNStatistic	getRkNNStatistics() Returns the statistic for performed rknn queries.
protected void	initializeCapacities(O object, boolean verbose) Determines the maximum and minimum number of entries in a node.
void	insert(List<O> objects) Inserts the specified objects into this MDkNNTree-Tree.
void	insert(O object) Inserts the specified object into this MDkNNTree-Tree.
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<QueryResult<D>>	reverseKNNQuery(O object, int k) Performs a reverse k-nearest neighbor query for the given object ID.
String[]	setParameters(String[] args) Sets the attributes of the class accordingly to the given parameters.
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.AbstractMTree

batchNN, choosePath, createEmptyRoot, delete, distance, doKNNQuery, getAttributeSettings, getDistanceFunction, getSortedEntries, getSortedEntries, insert, kNNQuery, postDelete, rangeQuery, setDatabase, toString

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

close, createHeader, description, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeFromFile, resetPageAccess

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning

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.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getParameters, getPossibleOptions, inlineDescription

Field Detail

K_P

public static final String K_P

Parameter k.

See Also:

Constant Field Values

K_D

public static final String K_D

Description for parameter k.

See Also:

Constant Field Values

k_max

int k_max

Parameter k.

log_k

private double[] log_k

The values of log(1),..,log(k_max)

rkNNStatistics

private RkNNStatistic rkNNStatistics

Provides some statistics about performed reverse knn-queries.

Constructor Detail

MkCoPTree

public MkCoPTree()

Creates a new MkCopTree.

Method Detail

insert

public void insert(O object)

Inserts the specified object into this MDkNNTree-Tree. This operation is not supported.

Specified by:

insert in interface Index<O extends DatabaseObject>

Overrides:

insert in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

object - the object to be inserted

preInsert

protected void preInsert(MkCoPEntry<D> entry)

Performs necessary operations before inserting the specified entry.

Specified by:

preInsert in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

entry - the entry to be inserted

insert

public void insert(List<O> objects)

Inserts the specified objects into this MDkNNTree-Tree.

Specified by:

insert in interface Index<O extends DatabaseObject>

Overrides:

insert in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

objects - the object to be inserted

reverseKNNQuery

public List<QueryResult<D>> reverseKNNQuery(O object,
                                            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.

Overrides:

reverseKNNQuery in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

object - the query object

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

getRkNNStatistics

public RkNNStatistic getRkNNStatistics()

Returns the statistic for performed rknn queries.

Returns:

the statistic for performed rknn queries

clearRkNNStatistics

public void clearRkNNStatistics()

Clears the values of the statistic for performed rknn queries

getK_max

public int getK_max()

Returns the value of the k_max parameter.

Returns:

the value of the k_max parameter

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Description copied from interface: Parameterizable

Sets the attributes of the class accordingly to the given parameters. Returns a new String array containing those entries of the given array that are neither expected nor used by this Parameterizable.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

initializeCapacities

protected void initializeCapacities(O object,
                                    boolean verbose)

Determines the maximum and minimum number of entries in a node.

Overrides:

initializeCapacities in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

See Also:

TreeIndex.initializeCapacities(DatabaseObject,boolean)

doReverseKNNQuery

private void doReverseKNNQuery(int k,
                               Integer q,
                               List<QueryResult<D>> result,
                               List<Integer> candidates)

Performs a reverse knn query.

Parameters:

k - the parametr 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)

getKNNList

private List<D> getKNNList(Integer id,
                           Map<Integer,KNNList<D>> knnLists)

adjustApproximatedKNNDistances

private void adjustApproximatedKNNDistances(MkCoPEntry<D> entry,
                                            Map<Integer,KNNList<D>> 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<D> entry,
                                     List<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

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,D> createNewLeafNode(int capacity)

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

protected MkCoPTreeNode<O,D> createNewDirectoryNode(int capacity)

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

createNewLeafEntry

protected MkCoPEntry<D> createNewLeafEntry(O object,
                                           D parentDistance)

Creates a new leaf entry representing the specified data object in the specified subtree.

Specified by:

createNewLeafEntry in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Parameters:

object - the data object to be represented by the new entry

parentDistance - the distance from the object to the routing object of the parent node

Returns:

the newly created leaf entry

createNewDirectoryEntry

protected MkCoPEntry<D> createNewDirectoryEntry(MkCoPTreeNode<O,D> node,
                                                Integer routingObjectID,
                                                D parentDistance)

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

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<D> createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D>>,MkCoPEntry<D extends NumberDistance<D>>>

Returns:

an entry representing the root node