diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query/knn')
9 files changed, 540 insertions, 91 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 index 296a3950..731148e8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java @@ -4,7 +4,7 @@ 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 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,11 +23,8 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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; @@ -53,18 +50,8 @@ public abstract class AbstractDistanceKNNQuery<O, D extends Distance<D>> extends } @Override - abstract public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k); - - @Override - abstract public List<DistanceResultPair<D>> getKNNForObject(O obj, int k); + abstract public KNNResult<D> getKNNForDBID(DBID id, int k); @Override - public DistanceQuery<O, D> getDistanceQuery() { - return distanceQuery; - } - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } + abstract public KNNResult<D> getKNNForObject(O obj, int k); }
\ 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 index 81b4ded8..80d91180 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java @@ -4,7 +4,7 @@ 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 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,9 +29,6 @@ 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; @@ -41,7 +38,7 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; * @author Erich Schubert * * @apiviz.landmark - * @apiviz.uses DistanceResultPair oneway - - «create» + * @apiviz.has KNNResult oneway - - «create» * * @param <O> Object type * @param <D> Distance type @@ -54,7 +51,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k); + public KNNResult<D> getKNNForDBID(DBID id, int k); /** * Bulk query method @@ -63,7 +60,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); + public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); /** * Bulk query method configured by a map. @@ -82,24 +79,5 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @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(); + public KNNResult<D> getKNNForObject(O obj, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java new file mode 100644 index 00000000..d45fd8d7 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java @@ -0,0 +1,83 @@ +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) 2012 + 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.Collection; +import java.util.List; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Interface for kNN results - List<> like. + * + * @author Erich Schubert + * + * @param <D> Distance type + * + * @apiviz.composedOf DistanceResultPair + */ +public interface KNNResult<D extends Distance<D>> extends Collection<DistanceResultPair<D>> { + /** + * Size + */ + @Override + public int size(); + + /** + * Get the K parameter (note: this may be less than the size of the list!) + * + * @return K + */ + public int getK(); + + /** + * Direct object access. + * + * @param index + */ + public DistanceResultPair<D> get(int index); + + /** + * Get the distance to the k nearest neighbor, or maxdist otherwise. + * + * @return Maximum distance + */ + public D getKNNDistance(); + + /** + * View as ArrayDBIDs + * + * @return Static DBIDs + */ + public ArrayDBIDs asDBIDs(); + + /** + * View as list of distances + * + * @return List of distances view + */ + public List<D> asDistanceList(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java new file mode 100644 index 00000000..1179edb5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java @@ -0,0 +1,417 @@ +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) 2012 + 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.AbstractCollection; +import java.util.AbstractList; +import java.util.Iterator; +import java.util.List; + +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.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Helper classes for kNN results. + * + * @author Erich Schubert + * + * @apiviz.uses KNNResult + */ +public final class KNNUtil { + /** + * Sublist of an existing result to contain only the first k elements. + * + * @author Erich Schubert + * + * @param <D> Distance + */ + protected static class KNNSubList<D extends Distance<D>> extends AbstractCollection<DistanceResultPair<D>> implements KNNResult<D> { + /** + * Parameter k + */ + private final int k; + + /** + * Actual size, including ties + */ + private final int size; + + /** + * Wrapped inner result. + */ + private final KNNResult<D> inner; + + /** + * Constructor. + * + * @param inner Inner instance + * @param k k value + */ + public KNNSubList(KNNResult<D> inner, int k) { + this.inner = inner; + this.k = k; + // Compute list size + // TODO: optimize for double distances. + { + DistanceResultPair<D> dist = inner.get(k); + int i = k; + while(i + 1 < inner.size()) { + if(dist.compareByDistance(inner.get(i + 1)) < 0) { + break; + } + i++; + } + size = i; + } + } + + @Override + public int getK() { + return k; + } + + @Override + public DistanceResultPair<D> get(int index) { + assert (index < size) : "Access beyond design size of list."; + return inner.get(index); + } + + @Override + public D getKNNDistance() { + return inner.get(k).getDistance(); + } + + @Override + public ArrayDBIDs asDBIDs() { + return KNNUtil.asDBIDs(this); + } + + @Override + public List<D> asDistanceList() { + return KNNUtil.asDistanceList(this); + } + + @Override + public Iterator<DistanceResultPair<D>> iterator() { + return new Itr(); + } + + @Override + public int size() { + return size; + } + + /** + * Iterator for the sublist. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private class Itr implements Iterator<DistanceResultPair<D>> { + /** + * Current position + */ + private int pos = -1; + + @Override + public boolean hasNext() { + return pos + 1 < size; + } + + @Override + public DistanceResultPair<D> next() { + pos++; + return inner.get(pos); + } + + @Override + public void remove() { + throw new UnsupportedOperationException("kNN results are unmodifiable."); + } + } + } + + /** + * Proxy iterator for accessing DBIDs. + * + * @author Erich Schubert + */ + protected static class DBIDIterator implements Iterator<DBID> { + /** + * The real iterator. + */ + Iterator<? extends DistanceResultPair<?>> itr; + + /** + * Constructor. + */ + protected DBIDIterator(Iterator<? extends DistanceResultPair<?>> itr) { + super(); + this.itr = itr; + } + + @Override + public boolean hasNext() { + return itr.hasNext(); + } + + @Override + public DBID next() { + return itr.next().getDBID(); + } + + @Override + public void remove() { + itr.remove(); + } + } + + /** + * Proxy iterator for accessing DBIDs. + * + * @author Erich Schubert + */ + protected static class DBIDItr implements DBIDIter { + /** + * Current result + */ + DistanceResultPair<?> cur; + + /** + * The real iterator. + */ + Iterator<? extends DistanceResultPair<?>> itr; + + /** + * Constructor. + */ + protected DBIDItr(Iterator<? extends DistanceResultPair<?>> itr) { + super(); + this.itr = itr; + advance(); + } + + @Override + public boolean valid() { + return cur != null; + } + + @Override + public void advance() { + if(itr.hasNext()) { + cur = itr.next(); + } + else { + cur = null; + } + } + + @Override + public int getIntegerID() { + return cur.getDBID().getIntegerID(); + } + + @Override + public DBID getDBID() { + return cur.getDBID(); + } + } + + /** + * A view on the DBIDs of the result + * + * @author Erich Schubert + */ + protected static class DBIDView implements ArrayDBIDs { + /** + * The true list. + */ + final KNNResult<?> parent; + + /** + * Constructor. + * + * @param parent Owner + */ + public DBIDView(KNNResult<?> parent) { + super(); + this.parent = parent; + } + + @Override + public DBID get(int i) { + return parent.get(i).getDBID(); + } + + @Override + public Iterator<DBID> iterator() { + return new DBIDIterator(parent.iterator()); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(parent.iterator()); + } + + @Override + public int size() { + return parent.size(); + } + + @Override + public boolean contains(DBID o) { + for(DBID id : this) { + if(id.equals(o)) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return parent.size() == 0; + } + + /** + * A binary search does not make sense here, as the (read-only) result is sorted by + * distance, not DBID. Thus unsupported. + */ + @Override + @Deprecated + public int binarySearch(DBID key) { + throw new UnsupportedOperationException("Since the result is usually not sorted, a binary Search does not make sense!"); + } + } + + /** + * Proxy iterator for accessing DBIDs. + * + * @author Erich Schubert + */ + protected static class DistanceItr<D extends Distance<D>> implements Iterator<D> { + /** + * The real iterator. + */ + Iterator<? extends DistanceResultPair<D>> itr; + + /** + * Constructor. + */ + protected DistanceItr(Iterator<? extends DistanceResultPair<D>> itr) { + super(); + this.itr = itr; + } + + @Override + public boolean hasNext() { + return itr.hasNext(); + } + + @Override + public D next() { + return itr.next().getDistance(); + } + + @Override + public void remove() { + itr.remove(); + } + } + + /** + * A view on the Distances of the result + * + * @author Erich Schubert + */ + protected static class DistanceView<D extends Distance<D>> extends AbstractList<D> implements List<D> { + /** + * The true list. + */ + final KNNResult<D> parent; + + /** + * Constructor. + * + * @param parent Owner + */ + public DistanceView(KNNResult<D> parent) { + super(); + this.parent = parent; + } + + @Override + public D get(int i) { + return parent.get(i).getDistance(); + } + + @Override + public Iterator<D> iterator() { + return new DistanceItr<D>(parent.iterator()); + } + + @Override + public int size() { + return parent.size(); + } + } + + /** + * View as ArrayDBIDs + * + * @param list Result to proxy + * @return Static DBIDs + */ + public static ArrayDBIDs asDBIDs(KNNResult<?> list) { + return new DBIDView(list); + } + + /** + * View as list of distances + * + * @param list Result to proxy + * @return List of distances view + */ + public static <D extends Distance<D>> List<D> asDistanceList(KNNResult<D> list) { + return new DistanceView<D>(list); + } + + /** + * Get a subset of the KNN result. + * + * @param list Existing list + * @param k k + * @return Subset + */ + public static <D extends Distance<D>> KNNResult<D> subList(KNNResult<D> list, int k) { + if(k >= list.size()) { + return list; + } + return new KNNSubList<D>(list, k); + } +}
\ 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 index b52c6dec..d6492f43 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java @@ -4,7 +4,7 @@ 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 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -32,7 +32,6 @@ 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; @@ -76,7 +75,7 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } @Override - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBID id, int k) { KNNHeap<D> heap = new KNNHeap<D>(k); if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) { O obj = relation.get(id); @@ -89,11 +88,11 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan heap.add(distanceQuery.distance(id, candidateID), candidateID); } } - return heap.toSortedArrayList(); + return heap.toKNNList(); } @Override - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNResult<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++) { @@ -101,9 +100,9 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } linearScanBatchKNN(ids, heaps); // Serialize heaps - List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(size); + List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(size); for(KNNHeap<D> heap : heaps) { - result.add(heap.toSortedArrayList()); + result.add(heap.toKNNList()); } return result; } @@ -121,12 +120,12 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } @Override - public List<DistanceResultPair<D>> getKNNForObject(O obj, int k) { + public KNNResult<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(); + return heap.toKNNList(); } }
\ 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 index 8af7e549..07632a34 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java @@ -4,7 +4,7 @@ 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 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,7 +30,6 @@ 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; @@ -75,12 +74,12 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } @Override - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBID id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNResult<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); @@ -90,9 +89,9 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } linearScanBatchKNN(objs, heaps); - List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(heaps.size()); + List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(heaps.size()); for(KNNHeap<D> heap : heaps) { - result.add(heap.toSortedArrayList()); + result.add(heap.toKNNList()); } return result; } 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 index 63652e5b..3f7dc04f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java @@ -4,7 +4,7 @@ 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 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,7 +27,6 @@ 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; @@ -57,12 +56,12 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD } @Override - public List<DistanceResultPair<DoubleDistance>> getKNNForDBID(DBID id, int k) { + public KNNResult<DoubleDistance> getKNNForDBID(DBID id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<DistanceResultPair<DoubleDistance>> getKNNForObject(O obj, int k) { + public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { @SuppressWarnings("unchecked") final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); // Optimization for double distances. @@ -78,7 +77,7 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD } } } - return heap.toSortedArrayList(); + return heap.toKNNList(); } @Override 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 index d82fc20e..93321609 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java @@ -4,7 +4,7 @@ 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 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -32,11 +32,9 @@ 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; @@ -46,11 +44,11 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @author Erich Schubert */ -public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { +public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { /** * The last preprocessor result */ - final private MaterializeKNNPreprocessor<O, D> preprocessor; + final private AbstractMaterializeKNNPreprocessor<O, D, T> preprocessor; /** * Warn only once. @@ -63,7 +61,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData * @param database Database to query * @param preprocessor Preprocessor instance to use */ - public PreprocessorKNNQuery(Relation<O> database, MaterializeKNNPreprocessor<O, D> preprocessor) { + public PreprocessorKNNQuery(Relation<O> database, AbstractMaterializeKNNPreprocessor<O, D, T> preprocessor) { super(database); this.preprocessor = preprocessor; } @@ -74,17 +72,17 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData * @param database Database to query * @param preprocessor Preprocessor to use */ - public PreprocessorKNNQuery(Relation<O> database, MaterializeKNNPreprocessor.Factory<O, D> preprocessor) { + public PreprocessorKNNQuery(Relation<O> database, AbstractMaterializeKNNPreprocessor.Factory<O, D, T> preprocessor) { this(database, preprocessor.instantiate(database)); } @Override - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + public KNNResult<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); + KNNResult<D> dr = preprocessor.get(id); int subk = k; D kdist = dr.get(subk - 1).getDistance(); while(subk < dr.size()) { @@ -98,7 +96,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } } if(subk < dr.size()) { - return dr.subList(0, subk); + return KNNUtil.subList(dr, subk); } else { return dr; @@ -108,14 +106,14 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } @Override - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNResult<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()); + List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(ids.size()); if(k < preprocessor.getK()) { for(DBID id : ids) { - List<DistanceResultPair<D>> dr = preprocessor.get(id); + KNNResult<D> dr = preprocessor.get(id); int subk = k; D kdist = dr.get(subk - 1).getDistance(); while(subk < dr.size()) { @@ -129,7 +127,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } } if(subk < dr.size()) { - result.add(dr.subList(0, subk)); + result.add(KNNUtil.subList(dr, subk)); } else { result.add(dr); @@ -156,7 +154,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } @Override - public List<DistanceResultPair<D>> getKNNForObject(O obj, int k) { + public KNNResult<D> getKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @@ -165,18 +163,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData * * @return preprocessor instance */ - public AbstractMaterializeKNNPreprocessor<O, D> getPreprocessor() { + public AbstractMaterializeKNNPreprocessor<O, D, T> 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 index 71d5433f..891ed296 100644 --- 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 @@ -7,7 +7,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2011 +Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |