diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query')
42 files changed, 581 insertions, 235 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java index bb913602..d9accf4f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -49,9 +49,9 @@ public abstract class AbstractDataBasedQuery<O> implements DatabaseQuery { } /** - * Give access to the underlying data query. + * Get the queries relation. * - * @return data query instance + * @return Relation */ public Relation<? extends O> getRelation() { return relation; diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java index 5d56a012..28c89ee3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java index ccdef3ef..e7403628 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java index 44f735ec..9b9367fb 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java index cbe2cb23..e0be7c40 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java index 19f17c48..4b838560 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java index 80f2c5b5..4cace1cf 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java index fff15c93..92c116e3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java index e29ccc5e..10dde0ad 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java index cf650b0f..2bb45623 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java index 63be8fe5..1986b246 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java index 6c056a0b..5015dee1 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java index 7013c693..4988c925 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java index c37c5b18..59f6534b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 @@ -60,28 +60,6 @@ public interface SpatialDistanceQuery<V extends SpatialComparable, D extends Dis D minDist(SpatialComparable mbr, DBID id); /** - * Computes the distance between the two given MBRs according to this distance - * function. - * - * @param mbr1 the first MBR object - * @param mbr2 the second MBR object - * @return the distance between the two given MBRs according to this distance - * function - */ - D mbrDist(SpatialComparable mbr1, SpatialComparable mbr2); - - /** - * Computes the distance between the centroids of the two given MBRs according - * to this distance function. - * - * @param mbr1 the first MBR object - * @param mbr2 the second MBR object - * @return the distance between the centroids of the two given MBRs according - * to this distance function - */ - D centerDistance(SpatialComparable mbr1, SpatialComparable mbr2); - - /** * Get the inner distance function. * * @return Distance function diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java index ddafc622..550c2c5c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 @@ -54,16 +54,6 @@ public class SpatialPrimitiveDistanceQuery<V extends SpatialComparable, D extend } @Override - public D centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return distanceFunction.centerDistance(mbr1, mbr2); - } - - @Override - public D mbrDist(SpatialComparable mbr1, SpatialComparable mbr2) { - return distanceFunction.minDist(mbr1, mbr2); - } - - @Override public D minDist(SpatialComparable mbr, V v) { return distanceFunction.minDist(mbr, v); } 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 71b54314..2257eb98 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 @@ -6,7 +6,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 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 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 42c9bab6..05c635a0 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 @@ -78,7 +78,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 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 e35cb99f..60426034 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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,10 +23,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; 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.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; @@ -63,18 +61,4 @@ public abstract class AbstractDistanceRangeQuery<O, D extends Distance<D>> exten @Override abstract public List<DistanceResultPair<D>> getRangeForObject(O obj, D range); - - @Override - public List<List<DistanceResultPair<D>>> getRangeForBulkDBIDs(ArrayDBIDs ids, D range) { - final List<List<DistanceResultPair<D>>> lists = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); - for(DBID id : ids) { - lists.add(getRangeForDBID(id, range)); - } - return lists; - } - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } }
\ No newline at end of file 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 6031a30e..dfe0b581 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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 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 d4b7296e..a7bb7db9 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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 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 b33c871e..18d1d173 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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 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 7d9ebd42..c2dbecd6 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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 @@ -25,11 +25,9 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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.query.DatabaseQuery; 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.distancevalue.Distance; /** @@ -54,15 +52,6 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range); /** - * Bulk query method - * - * @param ids query object IDs - * @param range Query range - * @return neighbors - */ - public List<List<DistanceResultPair<D>>> getRangeForBulkDBIDs(ArrayDBIDs ids, D range); - - /** * Get the nearest neighbors for a particular object in a given query range * * @param obj Query object @@ -70,16 +59,4 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { * @return neighbors */ public List<DistanceResultPair<D>> getRangeForObject(O obj, D range); - - /** - * Get the distance data type of the function. - */ - public D getDistanceFactory(); - - /** - * Access the underlying data query. - * - * @return data query in use - */ - public abstract Relation<? extends O> getRelation(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java index 21bd4f9a..a176e43d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/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 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 5cecaf88..86e82c7e 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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 @@ -54,9 +54,4 @@ public abstract class AbstractRKNNQuery<O, D extends Distance<D>> extends Abstra @Override abstract public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k); - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } }
\ 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 b3e581e7..1449d7f0 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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 @@ -35,6 +35,7 @@ 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.distancevalue.Distance; /** @@ -72,11 +73,11 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ ArrayList<DistanceResultPair<D>> rNNlist = new ArrayList<DistanceResultPair<D>>(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<List<DistanceResultPair<D>>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNResult<D>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; for(DBID qid : allIDs) { - List<DistanceResultPair<D>> knn = kNNLists.get(i); + KNNResult<D> knn = kNNLists.get(i); int last = Math.min(k - 1, knn.size() - 1); D dist = distanceQuery.distance(obj, qid); if(last < k - 1 || dist.compareTo(knn.get(last).getDistance()) < 1) { @@ -101,15 +102,15 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<List<DistanceResultPair<D>>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; for(DBID qid : allIDs) { - List<DistanceResultPair<D>> knn = kNNList.get(i); + KNNResult<D> knn = kNNList.get(i); for(DistanceResultPair<D> n : knn) { int j = 0; for(DBID id : ids) { - if(n.getDBID() == id) { + if(n.getDBID().equals(id)) { List<DistanceResultPair<D>> rNN = rNNList.get(j); rNN.add(new GenericDistanceResultPair<D>(n.getDistance(), qid)); } 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 5303666f..2f8e841a 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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.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.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor; import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNAndRKNNPreprocessor; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -98,18 +97,4 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } return result; } - - /** - * Get the preprocessor instance. - * - * @return preprocessor instance - */ - public AbstractMaterializeKNNPreprocessor<O, D> getPreprocessor() { - return preprocessor; - } - - @Override - public D getDistanceFactory() { - return preprocessor.getDistanceFactory(); - } }
\ No newline at end of file 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 df5ac43c..e707b6ce 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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,7 +29,6 @@ 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.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -69,16 +68,4 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @return reverse k nearest neighbors */ public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); - - /** - * Get the distance data type of the function. - */ - public D getDistanceFactory(); - - /** - * Access the underlying data query. - * - * @return data query in use - */ - public abstract Relation<? extends O> getRelation(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java index 80bcd988..a7e2bf37 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java index 2e263cd9..1af1c624 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java index 3dba474e..316d155c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java index 71dc0c4a..f57e0bd5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java index 91d7b84b..c3fdaaa4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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 diff --git a/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java index a6dca739..d601d0a4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java @@ -6,7 +6,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 |