← Back to branch summary

~ubuntu-branches/ubuntu/vivid/elki/vivid

« back to all changes in this revision

Viewing changes to src/de/lmu/ifi/dbs/elki/database/query/knn/DoubleOptimizedDistanceKNNQuery.java

  • Committer: Package Import Robot
  • Author(s): Erich Schubert
  • Date: 2014-01-22 16:23:20 UTC
  • mfrom: (1.1.8)
  • Revision ID: package-import@ubuntu.com-20140122162320-dtqtgcdiki8t9unc
Tags: 0.6.0-1
* New upstream final.
* 3DPC extension is not included, but may be uploaded as a separate
  package when there is actual need (it is a demo software, not meant
  for use outside of research, so just get the source code!)
* Upgrade to policy 3.9.5.0 (no changes)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/de/lmu/ifi/dbs/elki/database/query/knn/DoubleOptimizedDistanceKNNQuery.java
 
1
package de.lmu.ifi.dbs.elki.database.query.knn;
 
2
 
 
3
/*
 
4
 This file is part of ELKI:
 
5
 Environment for Developing KDD-Applications Supported by Index-Structures
 
6
 
 
7
 Copyright (C) 2013
 
8
 Ludwig-Maximilians-Universität München
 
9
 Lehr- und Forschungseinheit für Datenbanksysteme
 
10
 ELKI Development Team
 
11
 
 
12
 This program is free software: you can redistribute it and/or modify
 
13
 it under the terms of the GNU Affero General Public License as published by
 
14
 the Free Software Foundation, either version 3 of the License, or
 
15
 (at your option) any later version.
 
16
 
 
17
 This program is distributed in the hope that it will be useful,
 
18
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 
19
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
20
 GNU Affero General Public License for more details.
 
21
 
 
22
 You should have received a copy of the GNU Affero General Public License
 
23
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
24
 */
 
25
 
 
26
import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory;
 
27
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
 
28
import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
 
29
import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap;
 
30
import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList;
 
31
import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery;
 
32
import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery;
 
33
import de.lmu.ifi.dbs.elki.database.relation.Relation;
 
34
import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction;
 
35
import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
 
36
 
 
37
/**
 
38
 * Optimized linear scan query for {@link PrimitiveDoubleDistanceFunction}s.
 
39
 * 
 
40
 * @author Erich Schubert
 
41
 * 
 
42
 * @apiviz.uses PrimitiveDoubleDistanceFunction
 
43
 * 
 
44
 * @param <O> Object type
 
45
 */
 
46
public class DoubleOptimizedDistanceKNNQuery<O> extends AbstractDistanceKNNQuery<O, DoubleDistance> implements LinearScanQuery {
 
47
  /**
 
48
   * Raw distance function.
 
49
   */
 
50
  PrimitiveDoubleDistanceFunction<O> rawdist;
 
51
 
 
52
  /**
 
53
   * Constructor.newDoubleDistanceHeap
 
54
   * 
 
55
   * @param distanceQuery Distance function to use
 
56
   */
 
57
  @SuppressWarnings("unchecked")
 
58
  public DoubleOptimizedDistanceKNNQuery(PrimitiveDistanceQuery<O, DoubleDistance> distanceQuery) {
 
59
    super(distanceQuery);
 
60
    if(!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) {
 
61
      throw new UnsupportedOperationException("DoubleOptimizedKNNQuery instantiated for non-PrimitiveDoubleDistanceFunction!");
 
62
    }
 
63
    rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction();
 
64
  }
 
65
 
 
66
  @Override
 
67
  public DoubleDistanceKNNList getKNNForDBID(DBIDRef id, int k) {
 
68
    final Relation<? extends O> relation = this.relation;
 
69
    DoubleDistanceKNNHeap heap = DBIDFactory.FACTORY.newDoubleDistanceHeap(k);
 
70
    linearScan(relation, relation.iterDBIDs(), rawdist, relation.get(id), heap);
 
71
    return heap.toKNNList();
 
72
  }
 
73
 
 
74
  @Override
 
75
  public DoubleDistanceKNNList getKNNForObject(O obj, int k) {
 
76
    DoubleDistanceKNNHeap heap = DBIDFactory.FACTORY.newDoubleDistanceHeap(k);
 
77
    linearScan(relation, relation.iterDBIDs(), rawdist, obj, heap);
 
78
    return heap.toKNNList();
 
79
  }
 
80
 
 
81
  private static <O> void linearScan(Relation<? extends O> relation, DBIDIter iter, PrimitiveDoubleDistanceFunction<? super O> rawdist, final O obj, DoubleDistanceKNNHeap heap) {
 
82
    double kdist = Double.POSITIVE_INFINITY;
 
83
    while(iter.valid()) {
 
84
      final double dist = rawdist.doubleDistance(obj, relation.get(iter));
 
85
      if(dist <= kdist) {
 
86
        kdist = heap.insert(dist, iter);
 
87
      }
 
88
      iter.advance();
 
89
    }
 
90
  }
 
91
}