diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query/knn')
7 files changed, 731 insertions, 0 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java new file mode 100644 index 00000000..fb9b3702 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java @@ -0,0 +1,69 @@ +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.List; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Instance for the query on a particular database. + * + * @author Erich Schubert + */ +public abstract class AbstractDistanceKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { + /** + * Hold the distance function to be used. + */ + protected DistanceQuery<O, D> distanceQuery; + + /** + * Constructor. + * + * @param distanceQuery Distance query used + */ + public AbstractDistanceKNNQuery(DistanceQuery<O, D> distanceQuery) { + super(distanceQuery.getRelation()); + this.distanceQuery = distanceQuery; + } + + @Override + abstract public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k); + + @Override + abstract public List<DistanceResultPair<D>> getKNNForObject(O obj, int k); + + @Override + public DistanceQuery<O, D> getDistanceQuery() { + return distanceQuery; + } + + @Override + public D getDistanceFactory() { + return distanceQuery.getDistanceFactory(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java new file mode 100644 index 00000000..7bda2c85 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java @@ -0,0 +1,104 @@ +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.List; +import java.util.Map; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; + +/** + * The interface of an actual instance. + * + * @author Erich Schubert + * + * @apiviz.landmark + * @apiviz.uses DistanceResultPair oneway - - «create» + * + * @param <O> Object type + * @param <D> Distance type + */ +public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { + /** + * Get the k nearest neighbors for a particular id. + * + * @param id query object ID + * @param k Number of neighbors requested + * @return neighbors + */ + public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k); + + /** + * Bulk query method + * + * @param ids query object IDs + * @param k Number of neighbors requested + * @return neighbors + */ + public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); + + /** + * Bulk query method configured by a map. + * + * Warning: this API is not optimal, and might be removed soon (in fact, it is + * used in a single place) + * + * @param heaps Map of heaps to fill. + */ + public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps); + + /** + * Get the k nearest neighbors for a particular id. + * + * @param obj Query object + * @param k Number of neighbors requested + * @return neighbors + */ + // TODO: return KNNList<D> instead? + public List<DistanceResultPair<D>> getKNNForObject(O obj, int k); + + /** + * Get the distance query for this function. + */ + // TODO: remove? + public DistanceQuery<O, D> getDistanceQuery(); + + /** + * Get the distance data type of the function. + */ + public D getDistanceFactory(); + + /** + * Access the underlying data query. + * + * @return data query in use + */ + public abstract Relation<? extends O> getRelation(); +}
\ No newline at end of file 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java new file mode 100644 index 00000000..1d16f1af --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java @@ -0,0 +1,109 @@ +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.DBID; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +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. + * + * This is a subtle optimization: for primitive queries, it is clearly faster to + * retrieve the query object from the relation only once! + * + * @author Erich Schubert + * + * @apiviz.uses PrimitiveDistanceQuery + */ +public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> extends LinearScanKNNQuery<O, D> { + /** + * Constructor. + * + * @param distanceQuery Distance function to use + */ + public LinearScanPrimitiveDistanceKNNQuery(PrimitiveDistanceQuery<O, D> distanceQuery) { + super(distanceQuery); + } + + /** + * Perform a linear scan batch kNN for primitive distance functions. + * + * @param objs Objects list + * @param heaps Heaps array + */ + protected void linearScanBatchKNN(List<O> objs, List<KNNHeap<D>> heaps) { + final int size = objs.size(); + // Linear scan style KNN. + for(DBID candidateID : relation.iterDBIDs()) { + O candidate = relation.get(candidateID); + for(int index = 0; index < size; index++) { + O object = objs.get(index); + KNNHeap<D> heap = heaps.get(index); + heap.add(distanceQuery.distance(object, candidate), candidateID); + } + } + } + + @Override + public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + return getKNNForObject(relation.get(id), k); + } + + @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); + List<O> objs = new ArrayList<O>(size); + for(DBID id : ids) { + heaps.add(new KNNHeap<D>(k)); + objs.add(relation.get(id)); + } + linearScanBatchKNN(objs, heaps); + + List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(heaps.size()); + for(KNNHeap<D> heap : heaps) { + result.add(heap.toSortedArrayList()); + } + return result; + } + + @Override + public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { + List<O> objs = new ArrayList<O>(heaps.size()); + List<KNNHeap<D>> kheaps = new ArrayList<KNNHeap<D>>(heaps.size()); + for(Entry<DBID, KNNHeap<D>> ent : heaps.entrySet()) { + objs.add(relation.get(ent.getKey())); + kheaps.add(ent.getValue()); + } + linearScanBatchKNN(objs, kheaps); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java new file mode 100644 index 00000000..dff33e47 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java @@ -0,0 +1,108 @@ +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.Arrays; +import java.util.List; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; + +/** + * Optimized linear scan query for {@link PrimitiveDoubleDistanceFunction}s. + * + * @author Erich Schubert + * + * @apiviz.uses PrimitiveDoubleDistanceFunction + * + * @param <O> Object type + */ +public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveDistanceKNNQuery<O, DoubleDistance> { + /** + * Constructor. + * + * @param distanceQuery Distance function to use + */ + public LinearScanRawDoubleDistanceKNNQuery(PrimitiveDistanceQuery<O, DoubleDistance> distanceQuery) { + super(distanceQuery); + if(!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { + throw new UnsupportedOperationException("LinearScanRawDoubleDistance instantiated for non-RawDoubleDistance!"); + } + } + + @Override + public List<DistanceResultPair<DoubleDistance>> getKNNForDBID(DBID id, int k) { + return getKNNForObject(relation.get(id), k); + } + + @Override + public List<DistanceResultPair<DoubleDistance>> getKNNForObject(O obj, int k) { + @SuppressWarnings("unchecked") + final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); + // Optimization for double distances. + final KNNHeap<DoubleDistance> heap = new KNNHeap<DoubleDistance>(k); + double max = Double.POSITIVE_INFINITY; + for(DBID candidateID : relation.iterDBIDs()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(candidateID)); + if(doubleDistance <= max) { + heap.add(new DoubleDistanceResultPair(doubleDistance, candidateID)); + // Update cutoff + if(heap.size() >= heap.getK()) { + max = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); + } + } + } + return heap.toSortedArrayList(); + } + + @Override + protected void linearScanBatchKNN(List<O> objs, List<KNNHeap<DoubleDistance>> heaps) { + final int size = objs.size(); + @SuppressWarnings("unchecked") + final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); + // Track the max ourselves to reduce object access for comparisons. + final double[] max = new double[size]; + Arrays.fill(max, Double.POSITIVE_INFINITY); + + // The distance is computed on arbitrary vectors, we can reduce object + // loading by working on the actual vectors. + for(DBID candidateID : relation.iterDBIDs()) { + O candidate = relation.get(candidateID); + for(int index = 0; index < size; index++) { + final KNNHeap<DoubleDistance> heap = heaps.get(index); + double doubleDistance = rawdist.doubleDistance(objs.get(index), candidate); + if(doubleDistance <= max[index]) { + heap.add(new DoubleDistanceResultPair(doubleDistance, candidateID)); + if(heap.size() >= heap.getK()) { + max[index] = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); + } + } + } + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java new file mode 100644 index 00000000..b76d62a6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java @@ -0,0 +1,182 @@ +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.DBID; +import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor; +import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNPreprocessor; +import de.lmu.ifi.dbs.elki.logging.LoggingUtil; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; +import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; + +/** + * Instance for a particular database, invoking the preprocessor. + * + * @author Erich Schubert + */ +public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { + /** + * The last preprocessor result + */ + final private MaterializeKNNPreprocessor<O, D> preprocessor; + + /** + * Warn only once. + */ + private boolean warned = false; + + /** + * Constructor. + * + * @param database Database to query + * @param preprocessor Preprocessor instance to use + */ + public PreprocessorKNNQuery(Relation<O> database, MaterializeKNNPreprocessor<O, D> preprocessor) { + super(database); + this.preprocessor = preprocessor; + } + + /** + * Constructor. + * + * @param database Database to query + * @param preprocessor Preprocessor to use + */ + public PreprocessorKNNQuery(Relation<O> database, MaterializeKNNPreprocessor.Factory<O, D> preprocessor) { + this(database, preprocessor.instantiate(database)); + } + + @Override + public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + if(!warned && k > preprocessor.getK()) { + LoggingUtil.warning("Requested more neighbors than preprocessed!"); + } + if(!warned && k < preprocessor.getK()) { + List<DistanceResultPair<D>> dr = preprocessor.get(id); + int subk = k; + D kdist = dr.get(subk - 1).getDistance(); + while(subk < dr.size()) { + D ndist = dr.get(subk).getDistance(); + if(kdist.equals(ndist)) { + // Tie - increase subk. + subk++; + } + else { + break; + } + } + if(subk < dr.size()) { + return dr.subList(0, subk); + } + else { + return dr; + } + } + return preprocessor.get(id); + } + + @Override + public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + if(!warned && k > preprocessor.getK()) { + LoggingUtil.warning("Requested more neighbors than preprocessed!"); + } + List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); + if(k < preprocessor.getK()) { + for(DBID id : ids) { + List<DistanceResultPair<D>> dr = preprocessor.get(id); + int subk = k; + D kdist = dr.get(subk - 1).getDistance(); + while(subk < dr.size()) { + D ndist = dr.get(subk).getDistance(); + if(kdist.equals(ndist)) { + // Tie - increase subk. + subk++; + } + else { + break; + } + } + if(subk < dr.size()) { + result.add(dr.subList(0, subk)); + } + else { + result.add(dr); + } + } + } + else { + for(DBID id : ids) { + result.add(preprocessor.get(id)); + } + } + return result; + } + + @Override + public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { + for(Entry<DBID, KNNHeap<D>> ent : heaps.entrySet()) { + DBID id = ent.getKey(); + KNNHeap<D> heap = ent.getValue(); + for(DistanceResultPair<D> dr : preprocessor.get(id)) { + heap.add(dr); + } + } + } + + @SuppressWarnings("unused") + @Override + public List<DistanceResultPair<D>> getKNNForObject(O obj, int k) { + throw new AbortException("Preprocessor KNN query only supports ID queries."); + } + + /** + * Get the preprocessor instance. + * + * @return preprocessor instance + */ + public AbstractMaterializeKNNPreprocessor<O, D> getPreprocessor() { + return preprocessor; + } + + @Override + public D getDistanceFactory() { + return preprocessor.getDistanceFactory(); + } + + @Override + public DistanceQuery<O, D> getDistanceQuery() { + // TODO: remove? throw an exception? + return preprocessor.getDistanceQuery(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java new file mode 100644 index 00000000..71d5433f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java @@ -0,0 +1,28 @@ +/** + * <p>Prepared queries for k nearest neighbor (kNN) queries.</p> + * + * @apiviz.exclude de.lmu.ifi.dbs.elki.algorithm.* + */ +/* +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/>. +*/ +package de.lmu.ifi.dbs.elki.database.query.knn;
\ No newline at end of file |