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.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 FeatureVector 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

@Title(value="K-Nearest Neighbor Join")
@Description(value="Algorithm to find the k-nearest neighbors of each object in a spatial database")
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.

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.logging.AbstractLoggable

debug, logger

Constructor Summary

KNNJoin(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

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.

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

getDistanceFactory, 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.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

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.

k

int k

The k parameter

Constructor Detail

KNNJoin

public KNNJoin(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

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