Package elki.algorithm
Class KNNJoin
- java.lang.Object
-
- elki.algorithm.KNNJoin
-
- All Implemented Interfaces:
Algorithm
@Title("K-Nearest Neighbor Join") @Description("Algorithm to find the k-nearest neighbors of each object in a spatial database") @Priority(-10) public class KNNJoin extends java.lang.Object implements Algorithm
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.Since this method compares the MBR of every single leaf with every other leaf, it is essentially quadratic in the number of leaves, which may not be appropriate for large trees. It does currently not yet use the tree structure for pruning.
TODO: exploit the tree structure.
- Since:
- 0.1
- Author:
- Elke Achtert, Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
KNNJoin.Par
Parameterization class.private static class
KNNJoin.Task
Task in the processing queue.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field Description protected SpatialPrimitiveDistance<?>
distance
Distance function used.protected int
k
The k parameter.private static Logging
LOG
The logger for this class.
-
Constructor Summary
Constructors Constructor Description KNNJoin(SpatialPrimitiveDistance<?> distance, int k)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Relation<KNNList>
autorun(Database database)
Try to auto-run the algorithm on a database by calling a method calledrun
, with an optionalDatabase
first, and with data relations as specified byAlgorithm.getInputTypeRestriction()
.private double
computeStopDistance(java.util.List<KNNHeap> heaps)
Compute the maximum stop distance.TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.private java.util.List<KNNHeap>
initHeaps(SpatialPrimitiveDistance<?> distFunction, AbstractRStarTreeNode<?,?> pr)
Initialize the heaps.private void
processDataPages(SpatialPrimitiveDistance<?> df, java.util.List<KNNHeap> pr_heaps, java.util.List<KNNHeap> ps_heaps, AbstractRStarTreeNode<?,?> pr, AbstractRStarTreeNode<?,?> ps)
Processes the two data pages pr and ps and determines the k-nearest neighbors of pr in ps.Relation<KNNList>
run(Relation<? extends SpatialComparable> relation)
Joins in the given spatial database to each object its k-nearest neighbors.WritableDataStore<KNNList>
run(Relation<? extends SpatialComparable> relation, DBIDs ids)
Inner run method.WritableDataStore<KNNList>
run(AbstractRStarTree<?,?,?> idx, DBIDs ids)
Inner run method.
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
distance
protected SpatialPrimitiveDistance<?> distance
Distance function used.
-
k
protected int k
The k parameter.
-
-
Constructor Detail
-
KNNJoin
public KNNJoin(SpatialPrimitiveDistance<?> distance, int k)
Constructor.- Parameters:
distance
- Distance functionk
- k parameter
-
-
Method Detail
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Returns:
- Type restriction
-
autorun
public Relation<KNNList> autorun(Database database)
Description copied from interface:Algorithm
Try to auto-run the algorithm on a database by calling a method calledrun
, with an optionalDatabase
first, and with data relations as specified byAlgorithm.getInputTypeRestriction()
.
-
run
public Relation<KNNList> run(Relation<? extends SpatialComparable> relation)
Joins in the given spatial database to each object its k-nearest neighbors.- Parameters:
relation
- Relation to process- Returns:
- result
-
run
public WritableDataStore<KNNList> run(Relation<? extends SpatialComparable> relation, DBIDs ids)
Inner run method. This returns a double store, and is used byKNNJoinMaterializeKNNPreprocessor
- Parameters:
relation
- Data relationids
- Object IDs- Returns:
- Data store
-
run
public WritableDataStore<KNNList> run(AbstractRStarTree<?,?,?> idx, DBIDs ids)
Inner run method. This returns a double store, and is used byKNNJoinMaterializeKNNPreprocessor
- Parameters:
idx
- Index to processids
- Object IDs- Returns:
- Data store
-
initHeaps
private java.util.List<KNNHeap> initHeaps(SpatialPrimitiveDistance<?> distFunction, AbstractRStarTreeNode<?,?> pr)
Initialize the heaps.- Parameters:
distFunction
- Distance functionpr
- Node to initialize for- Returns:
- List of heaps
-
processDataPages
private void processDataPages(SpatialPrimitiveDistance<?> df, java.util.List<KNNHeap> pr_heaps, java.util.List<KNNHeap> ps_heaps, AbstractRStarTreeNode<?,?> pr, AbstractRStarTreeNode<?,?> ps)
Processes the two data pages pr and ps and determines the k-nearest neighbors of pr in ps.- Parameters:
df
- the distance function to usepr
- the first data pageps
- the second data pagepr_heaps
- the knn lists for each data objectps_heaps
- the knn lists for each data object in ps
-
computeStopDistance
private double computeStopDistance(java.util.List<KNNHeap> heaps)
Compute the maximum stop distance.- Parameters:
heaps
- Heaps list- Returns:
- the k-nearest neighbor distance of pr in ps
-
-