Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn
Class RdKNNTree<O extends NumberVector<O,?>,D extends NumberDistance<D>>

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.spatial.SpatialIndex<O,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>
                      extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,RdKNNNode<D>,RdKNNEntry<D>>
                          extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree<O,D>
All Implemented Interfaces:
Index<O>, Loggable, Parameterizable

public class RdKNNTree<O extends NumberVector<O,?>,D extends NumberDistance<D>>
extends NonFlatRStarTree<O,RdKNNNode<D>,RdKNNEntry<D>>

RDkNNTree is a spatial index structure based on the concepts of the R*-Tree supporting efficient processing of reverse k nearest neighbor queries. The k-nn distance is stored in each entry of a node.

todo: noch nicht fertig!!!

Author:
Elke Achtert

Field Summary
static String DEFAULT_DISTANCE_FUNCTION
          The default distance function.
static String DISTANCE_FUNCTION_D
          Description for parameter distance function.
static String DISTANCE_FUNCTION_P
          Parameter for distance function.
private  SpatialDistanceFunction<O,D> distanceFunction
          The distance function.
static String K_D
          Description for parameter k.
private  int k_max
          Parameter k.
static String K_P
          Parameter k.
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex
bulk, BULK_LOAD_D, BULK_LOAD_F, BULK_LOAD_STRATEGY_D, BULK_LOAD_STRATEGY_P, bulkLoadStrategy
 
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
RdKNNTree()
          Creates a new DeLiClu-Tree.
 
Method Summary
private  void adjustKNNDistance(RdKNNEntry<D> entry, Map<Integer,KNNList<D>> knnLists)
          Adjusts the knn distance in the subtree of the specified root entry.
protected  void bulkLoad(List<O> objects)
          Performs a bulk load on this RTree with the specified data.
protected  TreeIndexHeader createHeader()
          Creates a header for this index structure.
protected  RdKNNEntry<D> createNewDirectoryEntry(RdKNNNode<D> node)
          Creates a new directory entry representing the specified node.
protected  RdKNNNode<D> createNewDirectoryNode(int capacity)
          Creates a new directory node with the specified capacity.
protected  RdKNNEntry<D> createNewLeafEntry(O object)
          Creates a new leaf entry representing the specified data object.
protected  RdKNNNode<D> createNewLeafNode(int capacity)
          Creates a new leaf node with the specified capacity.
protected  RdKNNEntry<D> createRootEntry()
          Creates an entry representing the root node.
private  void doReverseKNN(RdKNNNode<D> node, O o, List<QueryResult<D>> result)
          Performs a reverse knn query in the specified subtree.
 List<AttributeSettings> getAttributeSettings()
          Returns the parameter setting of the attributes.
protected  void initializeCapacities(O object, boolean verbose)
          Determines the maximum and minimum number of entries in a node.
protected  void postDelete(O o)
          Performs necessary operations after deleting the specified object.
protected  void preInsert(RdKNNEntry<D> entry)
          Performs necessary operations before inserting the specified entry.
private  void preInsert(RdKNNEntry<D> q, RdKNNEntry<D> nodeEntry, KNNList<D> knns_q)
          Adapts the knn distances before insertion of entry q.
<T extends Distance<T>>
List<QueryResult<T>>
reverseKNNQuery(O object, int k, DistanceFunction<O,T> distanceFunction)
          Performs a reverse k-nearest neighbor query for the given object ID.
 void setDatabase(Database<O> database)
          Sets the databse in the distance function of this index.
 String[] setParameters(String[] args)
          Sets the attributes of the class accordingly to the given parameters.
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree
computeHeight, createEmptyRoot, hasOverflow, hasUnderflow
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree
batchNN, bulkKNNQueryForIDs, clearReinsertions, createLeafNodes, delete, doKNNQuery, findPathToObject, getHeight, getLeaves, getSortedEntries, getSortedEntries, getValues, initializeFromFile, insert, insert, kNNQuery, rangeQuery, setHeight, toString
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
close, description, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, 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

DEFAULT_DISTANCE_FUNCTION

public static final String DEFAULT_DISTANCE_FUNCTION
The default distance function.


DISTANCE_FUNCTION_P

public static final String DISTANCE_FUNCTION_P
Parameter for distance function.

See Also:
Constant Field Values

DISTANCE_FUNCTION_D

public static final String DISTANCE_FUNCTION_D
Description for parameter distance function.


k_max

private int k_max
Parameter k.


distanceFunction

private SpatialDistanceFunction<O extends NumberVector<O,?>,D extends NumberDistance<D>> distanceFunction
The distance function.

Constructor Detail

RdKNNTree

public RdKNNTree()
Creates a new DeLiClu-Tree.

Method Detail

preInsert

protected void preInsert(RdKNNEntry<D> entry)
Performs necessary operations before inserting the specified entry.

Specified by:
preInsert in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
entry - the entry to be inserted

postDelete

protected void postDelete(O o)
Performs necessary operations after deleting the specified object.

Specified by:
postDelete in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
o - the object to be deleted

bulkLoad

protected void bulkLoad(List<O> objects)
Performs a bulk load on this RTree with the specified data. Is called by the constructur and should be overwritten by subclasses if necessary.

Overrides:
bulkLoad in class NonFlatRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
objects - the data objects to be indexed

reverseKNNQuery

public <T extends Distance<T>> List<QueryResult<T>> reverseKNNQuery(O object,
                                                                    int k,
                                                                    DistanceFunction<O,T> distanceFunction)
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 AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
object - the query object
k - the number of nearest neighbors to be returned
distanceFunction - the distance function that computes the distances beween the objects
Returns:
a List of the query results

createHeader

protected TreeIndexHeader createHeader()
Description copied from class: TreeIndex
Creates a header for this index structure. Subclasses may need to overwrite this method.

Overrides:
createHeader in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Returns:
a header for this index structure
See Also:
TreeIndex.createHeader()

initializeCapacities

protected void initializeCapacities(O object,
                                    boolean verbose)
Description copied from class: TreeIndex
Determines the maximum and minimum number of entries in a node.

Overrides:
initializeCapacities in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<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(de.lmu.ifi.dbs.elki.data.DatabaseObject,boolean)

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 SpatialIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<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[])

getAttributeSettings

public List<AttributeSettings> getAttributeSettings()
Returns the parameter setting of the attributes.

Specified by:
getAttributeSettings in interface Parameterizable
Overrides:
getAttributeSettings in class AbstractParameterizable
Returns:
the parameter setting of the attributes
See Also:
Parameterizable.getAttributeSettings()

setDatabase

public void setDatabase(Database<O> database)
Sets the databse in the distance function of this index.

Specified by:
setDatabase in interface Index<O extends NumberVector<O,?>>
Overrides:
setDatabase in class SpatialIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
database - the database

preInsert

private void preInsert(RdKNNEntry<D> q,
                       RdKNNEntry<D> nodeEntry,
                       KNNList<D> knns_q)
Adapts the knn distances before insertion of entry q.

Parameters:
q - the entry to be inserted
nodeEntry - the entry representing the root of thge current subtree
knns_q - the knns of q

doReverseKNN

private void doReverseKNN(RdKNNNode<D> node,
                          O o,
                          List<QueryResult<D>> result)
Performs a reverse knn query in the specified subtree.

Parameters:
node - the root node of the current subtree
o - the id of the object for which the rknn query is performed
result - the list conrtaining the query results

adjustKNNDistance

private void adjustKNNDistance(RdKNNEntry<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

createNewLeafNode

protected RdKNNNode<D> createNewLeafNode(int capacity)
Creates a new leaf node with the specified capacity.

Specified by:
createNewLeafNode in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
capacity - the capacity of the new node
Returns:
a new leaf node

createNewDirectoryNode

protected RdKNNNode<D> createNewDirectoryNode(int capacity)
Creates a new directory node with the specified capacity.

Specified by:
createNewDirectoryNode in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
capacity - the capacity of the new node
Returns:
a new directory node

createNewLeafEntry

protected RdKNNEntry<D> createNewLeafEntry(O object)
Creates a new leaf entry representing the specified data object.

Specified by:
createNewLeafEntry in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
object - the data object to be represented by the new entry
Returns:
the newly created leaf entry

createNewDirectoryEntry

protected RdKNNEntry<D> createNewDirectoryEntry(RdKNNNode<D> node)
Creates a new directory entry representing the specified node.

Specified by:
createNewDirectoryEntry in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Parameters:
node - the node to be represented by the new entry
Returns:
the newly created directory entry

createRootEntry

protected RdKNNEntry<D> createRootEntry()
Creates an entry representing the root node.

Specified by:
createRootEntry in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
Returns:
an entry representing the root node

Release 0.1 (2008-07-10_1838)