de.lmu.ifi.dbs.elki.algorithm
Class KNNJoin<V extends NumberVector<V,?>,D extends Distance<D>,N extends SpatialNode<N,E>,E extends SpatialEntry>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O,R>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<V,D,AnnotationFromHashMap<KNNList<D>>>
                  de.lmu.ifi.dbs.elki.algorithm.KNNJoin<V,D,N,E>

Type Parameters:

V - the type of NumberVector handled by this Algorithm

D - the type of Distance used by this Algorithm

N - the type of node used in the spatial index structure

E - the type of entry used in the spatial node

All Implemented Interfaces:

Algorithm<V,AnnotationFromHashMap<KNNList<D>>>, Parameterizable

public class KNNJoin<V extends NumberVector<V,?>,D extends Distance<D>,N extends SpatialNode<N,E>,E extends SpatialEntry>
extends DistanceBasedAlgorithm<V,D,AnnotationFromHashMap<KNNList<D>>>

Joins in a given spatial database to each object its k-nearest neighbors. This algorithm only supports spatial databases based on a spatial index structure.

Author:

Elke Achtert

Field Summary

(package private) int	k The k parameter
static OptionID	K_ID OptionID for K_PARAM
IntParameter	K_PARAM Parameter that specifies the k-nearest neighbors to be assigned, must be an integer greater than 0.
static AssociationID<KNNList<?>>	KNNLIST Association ID for KNNLists.
private AnnotationFromHashMap<KNNList<D>>	result The knn lists for each object.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM

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

KNNJoin()
Provides a KNN-Join, adding parameter K_PARAM to the option handler additionally to parameters of super class.

Method Summary

Description	getDescription() Returns a description of the algorithm.
AnnotationFromHashMap<KNNList<D>>	getResult() Returns the result of the algorithm.
private D	processDataPages(N pr, N ps, HashMap<Integer,KNNList<D>> knnLists, D pr_knn_distance) Processes the two data pages pr and ps and determines the k-nearest neighbors of pr in ps.
protected AnnotationFromHashMap<KNNList<D>>	runInTime(Database<V> database) Joins in the given spatial database to each object its k-nearest neighbors.
List<String>	setParameters(List<String> args) Calls the super method and instantiates DistanceBasedAlgorithm.distanceFunction according to the value of parameter DistanceBasedAlgorithm.DISTANCE_FUNCTION_PARAM.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

isTime, isVerbose, run, setTime, setVerbose

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, toString, 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

public final IntParameter K_PARAM

Parameter that specifies the k-nearest neighbors to be assigned, must be an integer greater than 0.

Default value: 1

Key: -knnjoin.k

KNNLIST

public static final AssociationID<KNNList<?>> KNNLIST

Association ID for KNNLists.

result

private AnnotationFromHashMap<KNNList<D extends Distance<D>>> result

The knn lists for each object.

k

int k

The k parameter

Constructor Detail

KNNJoin

public KNNJoin()

Provides a KNN-Join, adding parameter K_PARAM to the option handler additionally to parameters of super class.

Method Detail

runInTime

protected AnnotationFromHashMap<KNNList<D>> runInTime(Database<V> database)
                                                                   throws IllegalStateException

Joins in the given spatial database to each object its k-nearest neighbors.

Specified by:

runInTime in class AbstractAlgorithm<V extends NumberVector<V,?>,AnnotationFromHashMap<KNNList<D extends Distance<D>>>>

Parameters:

database - the database to run the algorithm on

Returns:

the Result computed by this algorithm

Throws:

IllegalStateException - if the specified database is not an instance of SpatialIndexDatabase or the specified distance function is not an instance of SpatialDistanceFunction.

processDataPages

private D processDataPages(N pr,
                           N ps,
                           HashMap<Integer,KNNList<D>> knnLists,
                           D pr_knn_distance)

Processes the two data pages pr and ps and determines the k-nearest neighbors of pr in ps.

Parameters:

pr - the first data page

ps - the second data page

knnLists - the knn lists for each data object

pr_knn_distance - the current knn distance of data page pr

Returns:

the k-nearest neighbor distance of pr in ps

setParameters

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

Description copied from class: DistanceBasedAlgorithm

Calls the super method and instantiates DistanceBasedAlgorithm.distanceFunction according to the value of parameter DistanceBasedAlgorithm.DISTANCE_FUNCTION_PARAM. The remaining parameters are passed to the DistanceBasedAlgorithm.distanceFunction.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class DistanceBasedAlgorithm<V extends NumberVector<V,?>,D extends Distance<D>,AnnotationFromHashMap<KNNList<D extends Distance<D>>>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

a list containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

getResult

public AnnotationFromHashMap<KNNList<D>> getResult()

Returns the result of the algorithm.

Returns:

the result of the algorithm

getDescription

public Description getDescription()

Returns a description of the algorithm.

Returns:

a description of the algorithm