Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndex<O,D,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree<O,D,MkCoPTreeNode<O,D,N>,MkCoPEntry<D,N>>
                      extended by de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop.MkCoPTree<O,D,N>
Type Parameters:
O - Object type
D - Distance type
N - Number type
All Implemented Interfaces:
Index<O>, Parameterizable

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

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 OptionID K_ID
          OptionID for K_PARAM
(package private)  int k_max
          Parameter k.
private  IntParameter K_PARAM
          Parameter for k
private  double[] log_k
          The values of log(1),..
private  QueryStatistic rkNNStatistics
          Provides some statistics about performed reverse knn-queries.
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree
DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM, extraIntegrityChecks
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
CACHE_SIZE_ID, cacheSize, dirCapacity, dirMinimum, file, FILE_ID, initialized, leafCapacity, leafMinimum, PAGE_SIZE_ID, 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, logger
 
Constructor Summary
MkCoPTree()
          Creates a new MkCopTree.
 
Method Summary
private  void adjustApproximatedKNNDistances(MkCoPEntry<D,N> entry, Map<Integer,KNNList<D>> knnLists)
          Adjusts the knn distance in the subtree of the specified root entry.
private  void approximateKnnDistances(MkCoPLeafEntry<D,N> 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,N> createNewDirectoryEntry(MkCoPTreeNode<O,D,N> node, Integer routingObjectID, D parentDistance)
          Creates a new directory entry representing the specified node.
protected  MkCoPTreeNode<O,D,N> createNewDirectoryNode(int capacity)
          Creates a new directory node with the specified capacity.
protected  MkCoPEntry<D,N> createNewLeafEntry(O object, D parentDistance)
          Creates a new leaf entry representing the specified data object in the specified subtree.
protected  MkCoPTreeNode<O,D,N> createNewLeafNode(int capacity)
          Creates a new leaf node with the specified capacity.
protected  MkCoPEntry<D,N> createRootEntry()
          Creates an entry representing the root node.
private  void doReverseKNNQuery(int k, Integer q, List<DistanceResultPair<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)
           
 QueryStatistic 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,N> entry)
          Performs necessary operations before inserting the specified entry.
 List<DistanceResultPair<D>> reverseKNNQuery(O object, int k)
          Performs a reverse k-nearest neighbor query for the given object ID.
 List<String> setParameters(List<String> args)
          Calls TreeIndex#setParameters and instantiates AbstractMTree.distanceFunction according to the value of parameter AbstractMTree.DISTANCE_FUNCTION_PARAM.
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, createEmptyRoot, delete, distance, doKNNQuery, getDistanceFunction, getSortedEntries, getSortedEntries, insert, kNNQuery, postDelete, rangeQuery, setDatabase, toString
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
close, createHeader, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, initializeFromFile, resetPageAccess
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, progress, 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, collectOptions, getParameters, shortDescription
 

Field Detail

K_ID

public static final OptionID K_ID
OptionID for K_PARAM


K_PARAM

private final IntParameter K_PARAM
Parameter for k


k_max

int k_max
Parameter k.


log_k

private double[] log_k
The values of log(1),..,log(k_max)


rkNNStatistics

private QueryStatistic 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.

Parameters:
object - the object to be inserted

preInsert

protected void preInsert(MkCoPEntry<D,N> 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,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Parameters:
entry - the entry to be inserted

insert

public void insert(List<O> objects)
Inserts the specified objects into this MDkNNTree-Tree.

Parameters:
objects - the object to be inserted

reverseKNNQuery

public List<DistanceResultPair<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.

Specified by:
reverseKNNQuery in class MetricalIndex<O extends DatabaseObject,D extends NumberDistance<D,N>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Parameters:
object - the query object
k - the number of nearest neighbors to be returned
Returns:
a List of the query results

getRkNNStatistics

public QueryStatistic 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 List<String> setParameters(List<String> args)
                           throws ParameterException
Description copied from class: AbstractMTree
Calls TreeIndex#setParameters and instantiates AbstractMTree.distanceFunction according to the value of parameter AbstractMTree.DISTANCE_FUNCTION_PARAM. The remaining parameters are passed to the AbstractMTree.distanceFunction.

Specified by:
setParameters in interface Parameterizable
Overrides:
setParameters in class AbstractMTree<O extends DatabaseObject,D extends NumberDistance<D,N>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Parameters:
args - parameters to set the attributes accordingly to
Returns:
a list containing the unused parameters
Throws:
ParameterException - in case of wrong parameter-setting

initializeCapacities

protected void initializeCapacities(O object,
                                    boolean verbose)
Determines the maximum and minimum number of entries in a node.

Specified by:
initializeCapacities in class TreeIndex<O extends DatabaseObject,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Parameters:
object - an object that will be stored in the index
verbose - flag to allow verbose messages

doReverseKNNQuery

private void doReverseKNNQuery(int k,
                               Integer q,
                               List<DistanceResultPair<D>> result,
                               List<Integer> 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)

getKNNList

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

adjustApproximatedKNNDistances

private void adjustApproximatedKNNDistances(MkCoPEntry<D,N> 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,N> 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,N> 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,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Parameters:
capacity - the capacity of the new node
Returns:
a new leaf node

createNewDirectoryNode

protected MkCoPTreeNode<O,D,N> 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,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Parameters:
capacity - the capacity of the new node
Returns:
a new directory node

createNewLeafEntry

protected MkCoPEntry<D,N> 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,N>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
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,N> createNewDirectoryEntry(MkCoPTreeNode<O,D,N> 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,N>,MkCoPTreeNode<O extends DatabaseObject,D extends NumberDistance<D,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
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,N> 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,N>,N extends Number>,MkCoPEntry<D extends NumberDistance<D,N>,N extends Number>>
Returns:
an entry representing the root node

Release 0.2.1 (2009-07-13_1605)