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

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.spatial.SpatialIndex<O,N,E>
                  de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>
                      de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,RdKNNNode<D,N>,RdKNNEntry<D,N>>
                          de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree<O,D,N>

Type Parameters:

O - Object type

D - Distance type

N - Number type

All Implemented Interfaces:

Index<O>, Parameterizable

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

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 OptionID	DISTANCE_FUNCTION_ID OptionID for DISTANCE_FUNCTION_PARAM
private ClassParameter<SpatialDistanceFunction<O,D>>	DISTANCE_FUNCTION_PARAM Parameter for distance function
private SpatialDistanceFunction<O,D>	distanceFunction The distance function.
static OptionID	K_ID OptionID for K_PARAM
private int	k_max Parameter k.
private IntParameter	K_PARAM Parameter for k

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

extraIntegrityChecks

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

bulk, BULK_LOAD_ID, BULK_LOAD_STRATEGY_ID, bulkLoadStrategy

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

RdKNNTree()
Creates a new DeLiClu-Tree.

Method Summary

private void	adjustKNNDistance(RdKNNEntry<D,N> 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 which is an instance of TreeIndexHeader.
protected RdKNNEntry<D,N>	createNewDirectoryEntry(RdKNNNode<D,N> node) Creates a new directory entry representing the specified node.
protected RdKNNNode<D,N>	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected RdKNNEntry<D,N>	createNewLeafEntry(O object) Creates a new leaf entry representing the specified data object.
protected RdKNNNode<D,N>	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected RdKNNEntry<D,N>	createRootEntry() Creates an entry representing the root node.
private void	doReverseKNN(RdKNNNode<D,N> node, O o, List<DistanceResultPair<D>> result) Performs a reverse knn query in the specified subtree.
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,N> entry) Performs necessary operations before inserting the specified entry.
private void	preInsert(RdKNNEntry<D,N> q, RdKNNEntry<D,N> nodeEntry, KNNList<D> knns_q) Adapts the knn distances before insertion of entry q.
<T extends Distance<T>> List<DistanceResultPair<T>>	reverseKNNQuery(O object, int k, SpatialDistanceFunction<O,T> distanceFunction) Performs a reverse k-nearest neighbor query for the given object ID.
void	setDatabase(Database<O> database) Sets the database in the distance function of this index.
List<String>	setParameters(List<String> args) todo

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, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, 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

DEFAULT_DISTANCE_FUNCTION

public static final String DEFAULT_DISTANCE_FUNCTION

The default distance function.

DISTANCE_FUNCTION_ID

public static final OptionID DISTANCE_FUNCTION_ID

OptionID for DISTANCE_FUNCTION_PARAM

DISTANCE_FUNCTION_PARAM

private final ClassParameter<SpatialDistanceFunction<O extends NumberVector<O,?>,D extends NumberDistance<D,N>>> DISTANCE_FUNCTION_PARAM

Parameter for distance function

k_max

private int k_max

Parameter k.

distanceFunction

private SpatialDistanceFunction<O extends NumberVector<O,?>,D extends NumberDistance<D,N>> distanceFunction

The distance function.

Constructor Detail

RdKNNTree

public RdKNNTree()

Creates a new DeLiClu-Tree.

Method Detail

preInsert

protected void preInsert(RdKNNEntry<D,N> entry)

Performs necessary operations before inserting the specified entry.

Specified by:

preInsert in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

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 constructor and should be overwritten by subclasses if necessary.

Overrides:

bulkLoad in class NonFlatRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

objects - the data objects to be indexed

reverseKNNQuery

public <T extends Distance<T>> List<DistanceResultPair<T>> reverseKNNQuery(O object,
                                                                           int k,
                                                                           SpatialDistanceFunction<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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Type Parameters:

T - distance type

Parameters:

object - the query object

k - the number of nearest neighbors to be returned

distanceFunction - the distance function that computes the distances between 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 which is an instance of TreeIndexHeader. Subclasses may need to overwrite this method if they need a more specialized header.

Overrides:

createHeader in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Returns:

a new header for this index structure

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,N>,N extends Number>,RdKNNEntry<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

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException

Description copied from class: SpatialIndex

todo

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class SpatialIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D,N>,N extends Number>,RdKNNEntry<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

setDatabase

public void setDatabase(Database<O> database)

Sets the database 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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

database - the database

preInsert

private void preInsert(RdKNNEntry<D,N> q,
                       RdKNNEntry<D,N> 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 the current subtree

knns_q - the knns of q

doReverseKNN

private void doReverseKNN(RdKNNNode<D,N> node,
                          O o,
                          List<DistanceResultPair<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 containing the query results

adjustKNNDistance

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

createNewLeafNode

protected RdKNNNode<D,N> 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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

protected RdKNNNode<D,N> 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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

createNewLeafEntry

protected RdKNNEntry<D,N> 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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

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

Returns:

the newly created leaf entry

createNewDirectoryEntry

protected RdKNNEntry<D,N> createNewDirectoryEntry(RdKNNNode<D,N> 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,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Parameters:

node - the node to be represented by the new entry

Returns:

the newly created directory entry

createRootEntry

protected RdKNNEntry<D,N> createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D,N>,N extends Number>,RdKNNEntry<D extends NumberDistance<D,N>,N extends Number>>

Returns:

an entry representing the root node