diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query/range')
7 files changed, 179 insertions, 162 deletions
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 531fa09d..1a3687d6 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,10 +24,9 @@ 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.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.database.relation.Relation; /** * Abstract base class for range queries that use a distance query in their @@ -36,34 +35,34 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @param <O> Database object type - * @param <D> Distance type */ -public abstract class AbstractDistanceRangeQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements RangeQuery<O, D> { +public abstract class AbstractDistanceRangeQuery<O> implements RangeQuery<O> { + /** + * The data to use for this query + */ + final protected Relation<? extends O> relation; + /** * Hold the distance function to be used. */ - protected DistanceQuery<O, D> distanceQuery; + final protected DistanceQuery<O> distanceQuery; /** * Constructor. * * @param distanceQuery Distance query */ - public AbstractDistanceRangeQuery(DistanceQuery<O, D> distanceQuery) { - super(distanceQuery.getRelation()); + public AbstractDistanceRangeQuery(DistanceQuery<O> distanceQuery) { + super(); + this.relation = distanceQuery.getRelation(); this.distanceQuery = distanceQuery; } @Override - public DistanceDBIDList<D> getRangeForDBID(DBIDRef id, D range) { + public DoubleDBIDList getRangeForDBID(DBIDRef id, double range) { return getRangeForObject(relation.get(id), range); } @Override - abstract public DistanceDBIDList<D> getRangeForObject(O obj, D range); - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } + abstract public DoubleDBIDList getRangeForObject(O obj, double range); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/DoubleOptimizedDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/DoubleOptimizedDistanceRangeQuery.java deleted file mode 100644 index 90b867e3..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/DoubleOptimizedDistanceRangeQuery.java +++ /dev/null @@ -1,92 +0,0 @@ -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) 2013 - 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.DBIDIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDoubleDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.integer.DoubleDistanceIntegerDBIDList; -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.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Default linear scan range query class. - * - * @author Erich Schubert - * - * @apiviz.uses PrimitiveDoubleDistanceFunction - * - * @param <O> Database object type - */ -public class DoubleOptimizedDistanceRangeQuery<O> extends AbstractDistanceRangeQuery<O, DoubleDistance> implements LinearScanQuery { - /** - * Raw distance function. - */ - PrimitiveDoubleDistanceFunction<? super O> rawdist; - - /** - * Constructor. - * - * @param distanceQuery Distance function to use - */ - @SuppressWarnings("unchecked") - public DoubleOptimizedDistanceRangeQuery(DistanceQuery<O, DoubleDistance> distanceQuery) { - super(distanceQuery); - if(!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { - throw new UnsupportedOperationException("DoubleOptimizedRangeQuery instantiated for non-PrimitiveDoubleDistanceFunction!"); - } - rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); - } - - @Override - public DistanceDBIDList<DoubleDistance> getRangeForDBID(DBIDRef id, DoubleDistance range) { - final Relation<? extends O> relation = this.relation; - DoubleDistanceIntegerDBIDList result = new DoubleDistanceIntegerDBIDList(); - linearScan(relation, relation.iterDBIDs(), rawdist, relation.get(id), range.doubleValue(), result); - result.sort(); - return result; - } - - @Override - public DistanceDBIDList<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { - DoubleDistanceIntegerDBIDList result = new DoubleDistanceIntegerDBIDList(); - linearScan(relation, relation.iterDBIDs(), rawdist, obj, range.doubleValue(), result); - result.sort(); - return result; - } - - private static <O> void linearScan(Relation<? extends O> relation, DBIDIter iter, PrimitiveDoubleDistanceFunction<? super O> rawdist, O obj, double range, ModifiableDoubleDistanceDBIDList result) { - while(iter.valid()) { - final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); - if(doubleDistance <= range) { - result.add(doubleDistance, iter); - } - iter.advance(); - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanDistanceRangeQuery.java index 8830dd45..8747cebf 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanDistanceRangeQuery.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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,11 +25,11 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; 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.distancevalue.Distance; /** * Default linear scan range query class. @@ -40,24 +40,23 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.has DistanceQuery * * @param <O> Database object type - * @param <D> Distance type */ -public class LinearScanDistanceRangeQuery<O, D extends Distance<D>> extends AbstractDistanceRangeQuery<O, D> implements LinearScanQuery { +public class LinearScanDistanceRangeQuery<O> extends AbstractDistanceRangeQuery<O> implements LinearScanQuery { /** * Constructor. * * @param distanceQuery Distance function to use */ - public LinearScanDistanceRangeQuery(DistanceQuery<O, D> distanceQuery) { + public LinearScanDistanceRangeQuery(DistanceQuery<O> distanceQuery) { super(distanceQuery); } @Override - public DistanceDBIDList<D> getRangeForDBID(DBIDRef id, D range) { - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + public DoubleDBIDList getRangeForDBID(DBIDRef id, double range) { + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - D currentDistance = distanceQuery.distance(id, iter); - if(currentDistance.compareTo(range) <= 0) { + double currentDistance = distanceQuery.distance(id, iter); + if(currentDistance <= range) { result.add(currentDistance, iter); } } @@ -66,11 +65,11 @@ public class LinearScanDistanceRangeQuery<O, D extends Distance<D>> extends Abst } @Override - public DistanceDBIDList<D> getRangeForObject(O obj, D range) { - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + public DoubleDBIDList getRangeForObject(O obj, double range) { + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - D currentDistance = distanceQuery.distance(obj, iter); - if(currentDistance.compareTo(range) <= 0) { + double currentDistance = distanceQuery.distance(obj, iter); + if(currentDistance <= range) { result.add(currentDistance, iter); } } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanEuclideanDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanEuclideanDistanceRangeQuery.java new file mode 100644 index 00000000..a12a4368 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanEuclideanDistanceRangeQuery.java @@ -0,0 +1,104 @@ +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) 2014 + 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.data.NumberVector; +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.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; + +/** + * Optimized linear scan for Euclidean distance range queries. + * + * @author Erich Schubert + * + * @apiviz.uses SquaredEuclideanDistanceFunction + * + * @param <O> Database object type + */ +public class LinearScanEuclideanDistanceRangeQuery<O extends NumberVector> extends LinearScanPrimitiveDistanceRangeQuery<O> { + /** + * Squared Euclidean distance function. + */ + private static final SquaredEuclideanDistanceFunction SQUARED = SquaredEuclideanDistanceFunction.STATIC; + + /** + * Constructor. + * + * @param distanceQuery Distance function to use + */ + public LinearScanEuclideanDistanceRangeQuery(PrimitiveDistanceQuery<O> distanceQuery) { + super(distanceQuery); + } + + @Override + public DoubleDBIDList getRangeForDBID(DBIDRef id, double range) { + // Note: subtle optimization. Get "id" only once! + final O obj = relation.get(id); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + linearScan(relation, relation.iterDBIDs(), obj, range, result); + result.sort(); + return result; + } + + @Override + public DoubleDBIDList getRangeForObject(O obj, double range) { + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + linearScan(relation, relation.iterDBIDs(), obj, range, result); + result.sort(); + return result; + } + + /** + * Main loop for linear scan, + * + * @param relation Data relation + * @param iter Iterator + * @param obj Query object + * @param range Query radius + * @param result Output data structure + */ + private void linearScan(Relation<? extends O> relation, DBIDIter iter, O obj, double range, ModifiableDoubleDBIDList result) { + // Avoid a loss in numerical precision when using the squared radius: + final double upper = range * 1.0000001; + // This should be more precise, but slower: + // upper = MathUtil.floatToDoubleUpper((float)range); + final double sqrange = upper * upper; + while(iter.valid()) { + final double sqdistance = SQUARED.distance(obj, relation.get(iter)); + if(sqdistance <= sqrange) { + final double dist = Math.sqrt(sqdistance); + if(dist <= range) { // double check, as we increased the radius above + result.add(dist, iter); + } + } + iter.advance(); + } + } +}
\ 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 ab4dd2be..69d6a0b7 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,10 +25,12 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; 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.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction; /** * Default linear scan range query class. @@ -41,43 +43,57 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.uses PrimitiveDistanceQuery * * @param <O> Database object type - * @param <D> Distance type */ -public class LinearScanPrimitiveDistanceRangeQuery<O, D extends Distance<D>> extends AbstractDistanceRangeQuery<O, D> { +public class LinearScanPrimitiveDistanceRangeQuery<O> extends AbstractDistanceRangeQuery<O> { + /** + * Unboxed distance function. + */ + private PrimitiveDistanceFunction<? super O> rawdist; + /** * Constructor. * * @param distanceQuery Distance function to use */ - public LinearScanPrimitiveDistanceRangeQuery(PrimitiveDistanceQuery<O, D> distanceQuery) { + public LinearScanPrimitiveDistanceRangeQuery(PrimitiveDistanceQuery<O> distanceQuery) { super(distanceQuery); + rawdist = distanceQuery.getDistanceFunction(); } @Override - public DistanceDBIDList<D> getRangeForDBID(DBIDRef id, D range) { + public DoubleDBIDList getRangeForDBID(DBIDRef id, double range) { // Note: subtle optimization. Get "id" only once! final O obj = relation.get(id); - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - D currentDistance = distanceQuery.distance(obj, iter); - if(currentDistance.compareTo(range) <= 0) { - result.add(currentDistance, iter); - } - } + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + linearScan(relation, relation.iterDBIDs(), obj, range, result); result.sort(); return result; } @Override - public DistanceDBIDList<D> getRangeForObject(O obj, D range) { - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - D currentDistance = distanceQuery.distance(obj, iter); - if(currentDistance.compareTo(range) <= 0) { - result.add(currentDistance, iter); - } - } + public DoubleDBIDList getRangeForObject(O obj, double range) { + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + linearScan(relation, relation.iterDBIDs(), obj, range, result); result.sort(); return result; } + + /** + * Main loop for linear scan, + * + * @param relation Data relation + * @param iter Iterator + * @param obj Query object + * @param range Query radius + * @param result Output data structure + */ + private void linearScan(Relation<? extends O> relation, DBIDIter iter, O obj, double range, ModifiableDoubleDBIDList result) { + while(iter.valid()) { + final double distance = rawdist.distance(obj, relation.get(iter)); + if(distance <= range) { + result.add(distance, iter); + } + iter.advance(); + } + } }
\ No newline at end of file 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 3f21c5f8..364b79c2 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,9 +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.ids.distance.DistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * The interface for range queries @@ -34,12 +33,11 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @apiviz.landmark - * @apiviz.uses DistanceDBIDList oneway - - «create» + * @apiviz.uses DoubleDBIDList oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { +public interface RangeQuery<O> extends DatabaseQuery { /** * Get the nearest neighbors for a particular id in a given query range * @@ -47,7 +45,7 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param range Query range * @return neighbors */ - public DistanceDBIDList<D> getRangeForDBID(DBIDRef id, D range); + public DoubleDBIDList getRangeForDBID(DBIDRef id, double range); /** * Get the nearest neighbors for a particular object in a given query range @@ -56,12 +54,5 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param range Query range * @return neighbors */ - public DistanceDBIDList<D> getRangeForObject(O obj, D range); - - /** - * Get the distance factory for the given distance type. - * - * @return Distance factory. - */ - public D getDistanceFactory(); + public DoubleDBIDList getRangeForObject(O obj, double range); } 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 b2e3427d..d47d3ad4 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) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |