Import Upstream version 0.4.0~beta1

1 files changed, 131 insertions, 0 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java
new file mode 100644
index 00000000..d4a4dd73
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java
@@ -0,0 +1,131 @@
+package de.lmu.ifi.dbs.elki.database.query.knn;
+/*
+This file is part of ELKI:
+Environment for Developing KDD-Applications Supported by Index-Structures
+
+Copyright (C) 2011
+Ludwig-Maximilians-Universität München
+Lehr- und Forschungseinheit für Datenbanksysteme
+ELKI Development Team
+
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU Affero General Public License as published by
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU Affero General Public License for more details.
+
+You should have received a copy of the GNU Affero General Public License
+along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+
+import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs;
+import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs;
+import de.lmu.ifi.dbs.elki.database.ids.DBID;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
+import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair;
+import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery;
+import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery;
+import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap;
+
+/**
+ * Instance of this query for a particular database.
+ * 
+ * @author Erich Schubert
+ * 
+ * @apiviz.landmark
+ * @apiviz.has DistanceQuery
+ */
+public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> implements LinearScanQuery {
+  /**
+   * Constructor.
+   * 
+   * @param distanceQuery Distance function to use
+   */
+  public LinearScanKNNQuery(DistanceQuery<O, D> distanceQuery) {
+    super(distanceQuery);
+  }
+
+  /**
+   * Linear batch knn for arbitrary distance functions.
+   * 
+   * @param ids DBIDs to process
+   * @param heaps Heaps to store the results in
+   */
+  private void linearScanBatchKNN(ArrayDBIDs ids, List<KNNHeap<D>> heaps) {
+    // The distance is computed on database IDs
+    for(DBID candidateID : relation.iterDBIDs()) {
+      Integer index = -1;
+      for(DBID id : ids) {
+        index++;
+        KNNHeap<D> heap = heaps.get(index);
+        heap.add(distanceQuery.distance(id, candidateID), candidateID);
+      }
+    }
+  }
+
+  @Override
+  public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) {
+    KNNHeap<D> heap = new KNNHeap<D>(k);
+    if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) {
+      O obj = relation.get(id);
+      for(DBID candidateID : relation.iterDBIDs()) {
+        heap.add(distanceQuery.distance(obj, relation.get(candidateID)), candidateID);
+      }
+    }
+    else {
+      for(DBID candidateID : relation.iterDBIDs()) {
+        heap.add(distanceQuery.distance(id, candidateID), candidateID);
+      }
+    }
+    return heap.toSortedArrayList();
+  }
+
+  @Override
+  public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
+    final int size = ids.size();
+    final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size);
+    for(int i = 0; i < size; i++) {
+      heaps.add(new KNNHeap<D>(k));
+    }
+    linearScanBatchKNN(ids, heaps);
+    // Serialize heaps
+    List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(size);
+    for(KNNHeap<D> heap : heaps) {
+      result.add(heap.toSortedArrayList());
+    }
+    return result;
+  }
+
+  @Override
+  public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) {
+    final int size = heaps.size();
+    ArrayModifiableDBIDs ids = DBIDUtil.newArray(size);
+    List<KNNHeap<D>> kheaps = new ArrayList<KNNHeap<D>>(size);
+    for(Entry<DBID, KNNHeap<D>> ent : heaps.entrySet()) {
+      ids.add(ent.getKey());
+      kheaps.add(ent.getValue());
+    }
+    linearScanBatchKNN(ids, kheaps);
+  }
+
+  @Override
+  public List<DistanceResultPair<D>> getKNNForObject(O obj, int k) {
+    KNNHeap<D> heap = new KNNHeap<D>(k);
+    for(DBID candidateID : relation.iterDBIDs()) {
+      O candidate = relation.get(candidateID);
+      heap.add(distanceQuery.distance(obj, candidate), candidateID);
+    }
+    return heap.toSortedArrayList();
+  }
+}
\ No newline at end of file