diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query')
25 files changed, 168 insertions, 1168 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java deleted file mode 100644 index ead3eebc..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java +++ /dev/null @@ -1,41 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.query; - -/* - 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.List; - -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; - -/** - * Collection of objects and their distances. - * - * @author Erich Schubert - * - * @apiviz.composedOf DistanceResultPair - * - * @param <D> Distance type - */ -public interface DistanceDBIDResult<D extends Distance<D>> extends List<DistanceResultPair<D>> { - // Empty. TODO: add "sorted" property? -} diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java deleted file mode 100644 index b6cc129b..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java +++ /dev/null @@ -1,68 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.query; - -/* - 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 de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.pairs.PairInterface; - -/** - * Class that consists of a pair (distance, object ID) commonly returned for kNN - * and range queries. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public interface DistanceResultPair<D extends Distance<?>> extends PairInterface<D, DBID>, Comparable<DistanceResultPair<D>>, DBIDRef { - /** - * Getter for first - * - * @return first element in pair - */ - public D getDistance(); - - /** - * Setter for first - * - * @param first new value for first element - */ - public void setDistance(D first); - - /** - * Setter for second - * - * @param second new value for second element - */ - public void setID(DBID second); - - /** - * Compare value, but by distance only. - * - * @param o Other object - * @return comparison result, as by Double.compare(this, other) - */ - public int compareByDistance(DistanceResultPair<D> o); -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java deleted file mode 100644 index 23abc327..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java +++ /dev/null @@ -1,165 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.query; - -/* - 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 de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Optimized DistanceResultPair that avoids/postpones an extra layer of boxing - * for double values. - * - * @author Erich Schubert - */ -public class DoubleDistanceResultPair implements DistanceResultPair<DoubleDistance> { - /** - * Distance value - */ - double distance; - - /** - * Object ID - */ - DBID id; - - /** - * Constructor. - * - * @param distance Distance value - * @param id Object ID - */ - public DoubleDistanceResultPair(double distance, DBID id) { - super(); - this.distance = distance; - this.id = id; - } - - @Override - public DoubleDistance getDistance() { - return new DoubleDistance(distance); - } - - @Override - public void setDistance(DoubleDistance distance) { - this.distance = distance.doubleValue(); - } - - @Override - public DBID getDBID() { - return id; - } - - @Override - public int getIntegerID() { - return id.getIntegerID(); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return id.sameDBID(other); - } - - @Override - public int compareDBID(DBIDRef other) { - return id.compareDBID(other); - } - - @Override - public void setID(DBID id) { - this.id = id; - } - - /** - * @deprecated Use {@link #getDoubleDistance} or {@link #getDistance} for clearness. - */ - @Deprecated - @Override - public DoubleDistance getFirst() { - return getDistance(); - } - - /** - * @deprecated Use {@link #getDBID} for clearness. - */ - @Deprecated - @Override - public DBID getSecond() { - return id; - } - - @Override - public int compareByDistance(DistanceResultPair<DoubleDistance> o) { - if(o instanceof DoubleDistanceResultPair) { - DoubleDistanceResultPair od = (DoubleDistanceResultPair) o; - final int delta = Double.compare(distance, od.distance); - if(delta != 0) { - return delta; - } - } - else { - final int delta = Double.compare(distance, o.getDistance().doubleValue()); - if(delta != 0) { - return delta; - } - } - return 0; - } - - @Override - public int compareTo(DistanceResultPair<DoubleDistance> o) { - final int delta = this.compareByDistance(o); - if(delta != 0) { - return delta; - } - return id.compareTo(o.getDBID()); - } - - @Override - public boolean equals(Object obj) { - if(!(obj instanceof DistanceResultPair)) { - return false; - } - if(obj instanceof DoubleDistanceResultPair) { - DoubleDistanceResultPair ddrp = (DoubleDistanceResultPair) obj; - return distance == ddrp.distance && id.sameDBID(ddrp.id); - } - DistanceResultPair<?> other = (DistanceResultPair<?>) obj; - return other.getDistance().equals(distance) && id.sameDBID(other.getDBID()); - } - - /** - * Get the distance as double value. - * - * @return distance value - */ - public double getDoubleDistance() { - return distance; - } - - @Override - public String toString() { - return "DistanceResultPair(" + distance + ", " + id + ")"; - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java deleted file mode 100644 index 2283c401..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java +++ /dev/null @@ -1,68 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.query; - -/* - 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.ArrayList; -import java.util.Collection; - -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; - -/** - * Default class to keep a list of distance-object pairs. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class GenericDistanceDBIDList<D extends Distance<D>> extends ArrayList<DistanceResultPair<D>> implements DistanceDBIDResult<D> { - /** - * Serialization Version - */ - private static final long serialVersionUID = 1L; - - /** - * Constructor. - */ - public GenericDistanceDBIDList() { - super(); - } - - /** - * Constructor. - * - * @param c existing collection - */ - public GenericDistanceDBIDList(Collection<? extends DistanceResultPair<D>> c) { - super(c); - } - - /** - * Constructor. - * - * @param initialCapacity Capacity - */ - public GenericDistanceDBIDList(int initialCapacity) { - super(initialCapacity); - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java deleted file mode 100644 index 414f145a..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java +++ /dev/null @@ -1,131 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.query; - -/* - 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 de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; - -/** - * Trivial implementation using a generic pair. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class GenericDistanceResultPair<D extends Distance<D>> extends Pair<D, DBID> implements DistanceResultPair<D> { - /** - * Canonical constructor - * - * @param first Distance - * @param second Object ID - */ - public GenericDistanceResultPair(D first, DBID second) { - super(first, second); - } - - /** - * Getter for first - * - * @return first element in pair - */ - @Override - public final D getDistance() { - return first; - } - - /** - * Setter for first - * - * @param first new value for first element - */ - @Override - public final void setDistance(D first) { - this.first = first; - } - - /** - * Getter for second element in pair - * - * @return second element in pair - */ - @Override - public final DBID getDBID() { - return second; - } - - @Override - public int getIntegerID() { - return second.getIntegerID(); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return second.sameDBID(other); - } - - @Override - public int compareDBID(DBIDRef other) { - return second.compareDBID(other); - } - - /** - * Setter for second - * - * @param second new value for second element - */ - @Override - public final void setID(DBID second) { - this.second = second; - } - - @Override - public int compareByDistance(DistanceResultPair<D> o) { - return first.compareTo(o.getDistance()); - } - - @Override - public int compareTo(DistanceResultPair<D> o) { - final int ret = compareByDistance(o); - if(ret != 0) { - return ret; - } - return second.compareTo(o.getDBID()); - } - - @Override - public boolean equals(Object obj) { - if(!(obj instanceof DistanceResultPair)) { - return false; - } - DistanceResultPair<?> other = (DistanceResultPair<?>) obj; - return first.equals(other.getDistance()) && second.sameDBID(other.getDBID()); - } - - @Override - public String toString() { - return "DistanceResultPair(" + getFirst() + ", " + getSecond() + ")"; - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java index 2257eb98..fdd116b7 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java @@ -1,6 +1,7 @@ /** * <p>Prepared queries for distances.</p> * + * @apiviz.exclude .*Instance */ /* This file is part of ELKI: 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 e5df1452..0ac2e8ee 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 @@ -26,6 +26,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** 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 13bf58c2..5b517509 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 @@ -24,14 +24,12 @@ package de.lmu.ifi.dbs.elki.database.query.knn; */ 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.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; 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. @@ -61,17 +59,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<KNNResult<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); + public List<? extends KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); /** * Get the k nearest neighbors for a particular id. 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 deleted file mode 100644 index e7612fcc..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java +++ /dev/null @@ -1,84 +0,0 @@ -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.List; - -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -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 DistanceDBIDResult<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 - */ - @Override - 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 deleted file mode 100644 index 01deeaa0..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java +++ /dev/null @@ -1,429 +0,0 @@ -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.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.ids.DBIDRef; -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 AbstractList<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(); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return getIntegerID() == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = getIntegerID(); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); - } - } - - /** - * 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(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if(iter.sameDBID(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(DBIDRef 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 b51dad4c..29fa9931 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 @@ -25,20 +25,17 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; 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.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; 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. @@ -67,11 +64,10 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan private void linearScanBatchKNN(ArrayDBIDs ids, List<KNNHeap<D>> heaps) { // The distance is computed on database IDs for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - DBID candidateID = iter.getDBID(); int index = 0; - for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { KNNHeap<D> heap = heaps.get(index); - heap.add(distanceQuery.distance(iter2, candidateID), candidateID); + heap.add(distanceQuery.distance(iter2, iter), iter); index++; } } @@ -79,16 +75,29 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan @Override public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { - KNNHeap<D> heap = new KNNHeap<D>(k); + KNNHeap<D> heap = KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k); + D max = distanceQuery.getDistanceFactory().infiniteDistance(); if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) { O obj = relation.get(id); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.add(distanceQuery.distance(obj, relation.get(iter)), iter); + final D dist = distanceQuery.distance(obj, relation.get(iter)); + if(max.compareTo(dist) > 0) { + heap.add(dist, iter); + if(heap.size() >= k) { + max = heap.getKNNDistance(); + } + } } } else { for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.add(distanceQuery.distance(id, iter), iter); + final D dist = distanceQuery.distance(id, iter); + if(max.compareTo(dist) > 0) { + heap.add(dist, iter); + if(heap.size() >= k) { + max = heap.getKNNDistance(); + } + } } } return heap.toKNNList(); @@ -99,7 +108,7 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan 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)); + heaps.add(KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k)); } linearScanBatchKNN(ids, heaps); // Serialize heaps @@ -111,20 +120,8 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } @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 KNNResult<D> getKNNForObject(O obj, int k) { - KNNHeap<D> heap = new KNNHeap<D>(k); + KNNHeap<D> heap = KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { heap.add(distanceQuery.distance(obj, iter), iter); } 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 59987282..c4f09744 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 @@ -25,16 +25,15 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; 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. @@ -66,12 +65,10 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten final int size = objs.size(); // Linear scan style KNN. for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - DBID candidateID = iter.getDBID(); - O candidate = relation.get(candidateID); + O candidate = relation.get(iter); 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); + heaps.get(index).add(distanceQuery.distance(object, candidate), iter); } } } @@ -87,7 +84,7 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size); List<O> objs = new ArrayList<O>(size); for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - heaps.add(new KNNHeap<D>(k)); + heaps.add(KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k)); objs.add(relation.get(iter)); } linearScanBatchKNN(objs, heaps); @@ -98,15 +95,4 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } 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 index a10aaac5..5e5eae2f 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 @@ -23,16 +23,20 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; 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.distanceresultlist.AbstractKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericKNNList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.TiedTopBoundedHeap; /** * Optimized linear scan query for {@link PrimitiveDoubleDistanceFunction}s. @@ -45,15 +49,22 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; */ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveDistanceKNNQuery<O, DoubleDistance> { /** + * Raw distance function. + */ + PrimitiveDoubleDistanceFunction<O> rawdist; + + /** * Constructor. * * @param distanceQuery Distance function to use */ + @SuppressWarnings("unchecked") public LinearScanRawDoubleDistanceKNNQuery(PrimitiveDistanceQuery<O, DoubleDistance> distanceQuery) { super(distanceQuery); - if(!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { + if (!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { throw new UnsupportedOperationException("LinearScanRawDoubleDistance instantiated for non-RawDoubleDistance!"); } + rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); } @Override @@ -63,47 +74,70 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD @Override public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { - @SuppressWarnings("unchecked") - final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); + return getKNNForObjectBenchmarked(obj, k); + } + + /** + * This is the cleaner, supposedly faster implementation. + * + * @param obj Query object + * @param k Desired number of neighbors + * @return kNN result + */ + KNNResult<DoubleDistance> getKNNForObjectClean(O obj, int k) { // Optimization for double distances. - final KNNHeap<DoubleDistance> heap = new KNNHeap<DoubleDistance>(k); - double max = Double.POSITIVE_INFINITY; - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + final TiedTopBoundedHeap<DoubleDistanceDBIDPair> heap = new TiedTopBoundedHeap<DoubleDistanceDBIDPair>(k, DoubleDistanceKNNHeap.COMPARATOR); + final DBIDIter iter = relation.iterDBIDs(); + + // First k elements don't need checking. + double max = 0.; + for (int i = 0; i < k && iter.valid(); i++, iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); + heap.add(DBIDFactory.FACTORY.newDistancePair(doubleDistance, iter)); + max = Math.max(max, doubleDistance); + } + // Remaining elements + for (; iter.valid(); iter.advance()) { final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); - if(doubleDistance <= max) { - heap.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); - // Update cutoff - if(heap.size() >= heap.getK()) { - max = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); - } + if (doubleDistance <= max) { + heap.add(DBIDFactory.FACTORY.newDistancePair(doubleDistance, iter)); + } + if (doubleDistance < max) { + max = heap.peek().doubleDistance(); } } - return heap.toKNNList(); + return new DoubleDistanceKNNList(heap, k); } - @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(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - O candidate = relation.get(iter); - 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, iter.getDBID())); - if(heap.size() >= heap.getK()) { - max[index] = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); - } - } + /** + * It does not make sense, but this version is faster in our larger + * benchmarks. Apparently, some JIT optimization kicks in better. + * + * @param obj Query object + * @param k Desired number of neighbors + * @return kNN result + */ + KNNResult<DoubleDistance> getKNNForObjectBenchmarked(O obj, int k) { + // THIS SHOULD BE SLOWER THAN THE VERSION ABOVE, BUT ISN'T! + final TiedTopBoundedHeap<DistanceDBIDPair<DoubleDistance>> heap = new TiedTopBoundedHeap<DistanceDBIDPair<DoubleDistance>>(k, AbstractKNNHeap.COMPARATOR); + final DBIDIter iter = relation.iterDBIDs(); + // First k elements don't need checking. + double max = 0.; + for (int i = 0; i < k && iter.valid(); i++, iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); + heap.add(DBIDFactory.FACTORY.newDistancePair(new DoubleDistance(doubleDistance), iter)); + max = Math.max(max, doubleDistance); + } + // Remaining elements + for (; iter.valid(); iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); + if (doubleDistance <= max) { + heap.add(DBIDFactory.FACTORY.newDistancePair(new DoubleDistance(doubleDistance), iter)); + } + if (doubleDistance < max) { + max = heap.peek().getDistance().doubleValue(); } } + return new GenericKNNList<DoubleDistance>(heap, k); } -}
\ 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 index 09f93945..a1e12fc3 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 @@ -25,20 +25,17 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; 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.logging.LoggingUtil; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** @@ -145,17 +142,6 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult< } @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); - } - } - } - - @Override public KNNResult<D> getKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } 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 891ed296..63c3aa16 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 @@ -2,6 +2,7 @@ * <p>Prepared queries for k nearest neighbor (kNN) queries.</p> * * @apiviz.exclude de.lmu.ifi.dbs.elki.algorithm.* + * @apiviz.exclude java.util.* */ /* This file is part of ELKI: @@ -25,4 +26,4 @@ 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 +package de.lmu.ifi.dbs.elki.database.query.knn; diff --git a/src/de/lmu/ifi/dbs/elki/database/query/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/package-info.java index 05c635a0..386ce6f3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/package-info.java @@ -73,6 +73,9 @@ * knnQuery.getKNNForDBID(id, 10); * } * }</pre></blockquote> + * + * @apiviz.exclude java.util.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.utilities.* */ /* This file is part of ELKI: @@ -96,4 +99,4 @@ 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;
\ No newline at end of file +package de.lmu.ifi.dbs.elki.database.query; diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java index 871c5e9e..9997f3d6 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java @@ -25,8 +25,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java index 758d603e..57fa2338 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java @@ -24,8 +24,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; */ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java index c8ddb1ec..13e13a5c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java @@ -23,15 +23,12 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; 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.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -61,10 +58,10 @@ public class LinearScanRangeQuery<O, D extends Distance<D>> extends AbstractDist for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { D currentDistance = distanceQuery.distance(id, iter); if(currentDistance.compareTo(range) <= 0) { - result.add(new GenericDistanceResultPair<D>(currentDistance, iter.getDBID())); + result.add(currentDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } @@ -74,10 +71,10 @@ public class LinearScanRangeQuery<O, D extends Distance<D>> extends AbstractDist for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { D currentDistance = distanceQuery.distance(obj, iter); if(currentDistance.compareTo(range) <= 0) { - result.add(new GenericDistanceResultPair<D>(currentDistance, iter.getDBID())); + result.add(currentDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java index c5ce2f55..18863b2d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java @@ -23,17 +23,14 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; 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.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; /** @@ -63,14 +60,14 @@ public class LinearScanRawDoubleDistanceRangeQuery<O> extends LinearScanRangeQue double epsilon = range.doubleValue(); O qo = relation.get(id); - GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { double doubleDistance = rawdist.doubleDistance(qo, relation.get(iter)); if(doubleDistance <= epsilon) { - result.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); + result.add(doubleDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } else { @@ -85,14 +82,14 @@ public class LinearScanRawDoubleDistanceRangeQuery<O> extends LinearScanRangeQue PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); double epsilon = range.doubleValue(); - GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); if(doubleDistance <= epsilon) { - result.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); + result.add(doubleDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } else { diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java index 2c6842bf..9574cda7 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java @@ -25,7 +25,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java index fe4f49e1..a090b466 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java @@ -23,12 +23,10 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -53,5 +51,5 @@ public abstract class AbstractRKNNQuery<O, D extends Distance<D>> extends Abstra } @Override - abstract public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k); + abstract public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java index 1f901828..f0e33777 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java @@ -24,20 +24,19 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; */ import java.util.ArrayList; -import java.util.Collections; 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.ids.DBIDRef; 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.GenericDistanceResultPair; 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.knn.KNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultIter; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -71,8 +70,8 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } @Override - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k) { - ArrayList<DistanceResultPair<D>> rNNlist = new ArrayList<DistanceResultPair<D>>(); + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k) { + GenericDistanceDBIDList<D> rNNlist = new GenericDistanceDBIDList<D>(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); List<? extends KNNResult<D>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); @@ -83,17 +82,17 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ int last = Math.min(k - 1, knn.size() - 1); D dist = distanceQuery.distance(obj, iter); if(last < k - 1 || dist.compareTo(knn.get(last).getDistance()) < 1) { - rNNlist.add(new GenericDistanceResultPair<D>(dist, iter.getDBID())); + rNNlist.add(dist, iter); } i++; } - Collections.sort(rNNlist); + rNNlist.sort(); return rNNlist; } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { - ArrayList<DistanceResultPair<D>> rNNList = new ArrayList<DistanceResultPair<D>>(); + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k) { + GenericDistanceDBIDList<D> rNNList = new GenericDistanceDBIDList<D>(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); @@ -101,22 +100,22 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ int i = 0; for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { KNNResult<D> knn = kNNList.get(i); - for(DistanceResultPair<D> n : knn) { - if(n.sameDBID(id)) { - rNNList.add(new GenericDistanceResultPair<D>(n.getDistance(), iter.getDBID())); + for(DistanceDBIDResultIter<D> n = knn.iter(); n.valid(); n.advance()) { + if(DBIDUtil.equal(n, id)) { + rNNList.add(n.getDistance(), iter); } } i++; } - Collections.sort(rNNList); + rNNList.sort(); return rNNList; } @Override - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { - List<List<DistanceResultPair<D>>> rNNList = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); + public List<GenericDistanceDBIDList<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + List<GenericDistanceDBIDList<D>> rNNList = new ArrayList<GenericDistanceDBIDList<D>>(ids.size()); for(int i = 0; i < ids.size(); i++) { - rNNList.add(new ArrayList<DistanceResultPair<D>>()); + rNNList.add(new GenericDistanceDBIDList<D>()); } ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); @@ -124,14 +123,13 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ int i = 0; for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { - DBID qid = iter.getDBID(); KNNResult<D> knn = kNNList.get(i); - for(DistanceResultPair<D> n : knn) { + for(DistanceDBIDResultIter<D> n = knn.iter(); n.valid(); n.advance()) { int j = 0; for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { - if(n.getDBID().sameDBID(iter2)) { - List<DistanceResultPair<D>> rNN = rNNList.get(j); - rNN.add(new GenericDistanceResultPair<D>(n.getDistance(), qid)); + if(DBIDUtil.equal(n, iter2)) { + GenericDistanceDBIDList<D> rNN = rNNList.get(j); + rNN.add(n.getDistance(), iter); } j++; } @@ -139,8 +137,7 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ i++; } for(int j = 0; j < ids.size(); j++) { - List<DistanceResultPair<D>> rNN = rNNList.get(j); - Collections.sort(rNN); + rNNList.get(j).sort(); } return rNNList; } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java index ab8c3b30..8256ffad 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java @@ -30,8 +30,8 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNAndRKNNPreprocessor; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; @@ -75,7 +75,7 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k) { if(!warned && k != preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } @@ -83,18 +83,18 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } @Override - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k) { + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @Override - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<? extends DistanceDBIDResult<D>> getRKNNForBulkDBIDs(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<DistanceDBIDResult<D>> result = new ArrayList<DistanceDBIDResult<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - result.add(preprocessor.getRKNN(iter.getDBID())); + result.add(preprocessor.getRKNN(iter)); } return result; } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java index 9ff6f790..dc21948e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java @@ -28,7 +28,7 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * * @author Erich Schubert * - * @apiviz.uses DistanceResultPair oneway - - «create» + * @apiviz.uses DistanceDBIDResult oneway - - «create» * * @param <O> Object type * @param <D> Distance type @@ -49,7 +49,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k); + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k); /** * Get the reverse k nearest neighbors for a particular object. @@ -58,7 +58,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k); + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k); /** * Bulk query method for reverse k nearest neighbors for ids. @@ -67,5 +67,5 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); + public List<? extends DistanceDBIDResult<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); }
\ No newline at end of file |