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>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<V,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>, Loggable, Parameterizable

public class KNNJoin<V extends NumberVector<V,?>,D extends Distance<D>,N extends SpatialNode<N,E>,E extends SpatialEntry>
extends DistanceBasedAlgorithm<V,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

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.
private KNNJoinResult<V,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

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.
Result<V>	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 neighors of pr in ps.
protected void	runInTime(Database<V> database) Runs the algorithm.

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

getAttributeSettings, getDistanceFunction, setParameters

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

description, isTime, isVerbose, run, setTime, setVerbose

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

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getParameters, getPossibleOptions, inlineDescription

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

result

private KNNJoinResult<V extends NumberVector<V,?>,D extends Distance<D>> result

The knn lists for each object.

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 void runInTime(Database<V> database)
                  throws IllegalStateException

Runs the algorithm.

Specified by:

runInTime in class AbstractAlgorithm<V extends NumberVector<V,?>>

Parameters:

database - the database to run the algorithm on

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

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 neighors 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

getResult

public Result<V> 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