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 .
*/
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> extends AbstractDistanceKNNQuery implements LinearScanQuery {
/**
* Constructor.
*
* @param distanceQuery Distance function to use
*/
public LinearScanKNNQuery(DistanceQuery 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> heaps) {
// The distance is computed on database IDs
for(DBID candidateID : relation.iterDBIDs()) {
Integer index = -1;
for(DBID id : ids) {
index++;
KNNHeap heap = heaps.get(index);
heap.add(distanceQuery.distance(id, candidateID), candidateID);
}
}
}
@Override
public List> getKNNForDBID(DBID id, int k) {
KNNHeap heap = new KNNHeap(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>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
final int size = ids.size();
final List> heaps = new ArrayList>(size);
for(int i = 0; i < size; i++) {
heaps.add(new KNNHeap(k));
}
linearScanBatchKNN(ids, heaps);
// Serialize heaps
List>> result = new ArrayList>>(size);
for(KNNHeap heap : heaps) {
result.add(heap.toSortedArrayList());
}
return result;
}
@Override
public void getKNNForBulkHeaps(Map> heaps) {
final int size = heaps.size();
ArrayModifiableDBIDs ids = DBIDUtil.newArray(size);
List> kheaps = new ArrayList>(size);
for(Entry> ent : heaps.entrySet()) {
ids.add(ent.getKey());
kheaps.add(ent.getValue());
}
linearScanBatchKNN(ids, kheaps);
}
@Override
public List> getKNNForObject(O obj, int k) {
KNNHeap heap = new KNNHeap(k);
for(DBID candidateID : relation.iterDBIDs()) {
O candidate = relation.get(candidateID);
heap.add(distanceQuery.distance(obj, candidate), candidateID);
}
return heap.toSortedArrayList();
}
}