diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query')
40 files changed, 754 insertions, 741 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 deleted file mode 100644 index 5d0e8444..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java +++ /dev/null @@ -1,59 +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) 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.relation.Relation; - -/** - * Abstract query bound to a certain representation. - * - * @author Erich Schubert - * - * @param <O> Database object type - */ -public abstract class AbstractDataBasedQuery<O> implements DatabaseQuery { - /** - * The data to use for this query - */ - final protected Relation<? extends O> relation; - - /** - * Database this query works on. - * - * @param relation Representation - */ - public AbstractDataBasedQuery(Relation<? extends O> relation) { - super(); - this.relation = relation; - } - - /** - * Get the queries relation. - * - * @return Relation - */ - public Relation<? extends O> getRelation() { - return relation; - } -}
\ No newline at end of file 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 caba81e3..f88261a8 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) 2013 + Copyright (C) 2014 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 8906e07c..f0bc7e9a 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,17 +25,15 @@ package de.lmu.ifi.dbs.elki.database.query; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.similarity.SimilarityQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** - * Interface that is a combination of distance and a similarity function. - * For combined implementations of both. + * Interface that is a combination of distance and a similarity function. For + * combined implementations of both. * * @author Erich Schubert - * + * * @param <O> Object type - * @param <D> Distance type */ -public interface DistanceSimilarityQuery<O, D extends Distance<D>> extends DistanceQuery<O, D>, SimilarityQuery<O, D> { +public interface DistanceSimilarityQuery<O> extends DistanceQuery<O>, SimilarityQuery<O> { // Empty } 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 6cb35025..e55e7d19 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) 2013 + Copyright (C) 2014 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 f530b72a..2edd9d0b 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) 2013 + Copyright (C) 2014 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.distance; 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.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Run a database query in a database context. @@ -34,9 +32,8 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @param <O> Database object type. - * @param <D> Distance result type. */ -public abstract class AbstractDatabaseDistanceQuery<O, D extends Distance<D>> extends AbstractDistanceQuery<O, D> { +public abstract class AbstractDatabaseDistanceQuery<O> extends AbstractDistanceQuery<O> { /** * Constructor. * @@ -47,25 +44,25 @@ public abstract class AbstractDatabaseDistanceQuery<O, D extends Distance<D>> ex } @Override - public D distance(O o1, DBIDRef id2) { - if(o1 instanceof DBID) { - return distance((DBID) o1, id2); + public double distance(O o1, DBIDRef id2) { + if(o1 instanceof DBIDRef) { + return distance((DBIDRef) o1, id2); } throw new UnsupportedOperationException("This distance function is only defined for known DBIDs."); } @Override - public D distance(DBIDRef id1, O o2) { - if(o2 instanceof DBID) { - return distance(id1, (DBID) o2); + public double distance(DBIDRef id1, O o2) { + if(o2 instanceof DBIDRef) { + return distance(id1, (DBIDRef) o2); } throw new UnsupportedOperationException("This distance function is only defined for known DBIDs."); } @Override - public D distance(O o1, O o2) { - if(o1 instanceof DBID && o2 instanceof DBID) { - return distance((DBID) o1, (DBID) o2); + public double distance(O o1, O o2) { + if(o1 instanceof DBIDRef && o2 instanceof DBIDRef) { + return distance((DBIDRef) o1, (DBIDRef) o2); } throw new UnsupportedOperationException("This distance function is only defined for known DBIDs."); } 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 933bd0d3..8f35eb58 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,9 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; */ 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.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * A distance query serves as adapter layer for database and primitive @@ -35,16 +33,21 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @param O Input object type - * @param D Distance result type */ -public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements DistanceQuery<O, D> { +public abstract class AbstractDistanceQuery<O> implements DistanceQuery<O> { + /** + * The data to use for this query + */ + final protected Relation<? extends O> relation; + /** * Constructor. * * @param relation Relation to use. */ public AbstractDistanceQuery(Relation<? extends O> relation) { - super(relation); + super(); + this.relation = relation; } /** @@ -55,7 +58,7 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(DBIDRef id1, DBIDRef id2); + public abstract double distance(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -65,7 +68,7 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(O o1, DBIDRef id2); + public abstract double distance(O o1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -75,7 +78,7 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(DBIDRef id1, O o2); + public abstract double distance(DBIDRef id1, O o2); /** * Returns the distance between the two objects specified by their object ids. @@ -85,40 +88,10 @@ public abstract class AbstractDistanceQuery<O, D extends Distance<D>> extends Ab * @return the distance between the two objects specified by their object ids */ @Override - public abstract D distance(O o1, O o2); - - @Override - public D getDistanceFactory() { - return getDistanceFunction().getDistanceFactory(); - } + public abstract double distance(O o1, O o2); - /** - * Provides an infinite distance. - * - * @return an infinite distance - */ - @Override - public D infiniteDistance() { - return getDistanceFunction().getDistanceFactory().infiniteDistance(); - } - - /** - * Provides a null distance. - * - * @return a null distance - */ - @Override - public D nullDistance() { - return getDistanceFunction().getDistanceFactory().nullDistance(); - } - - /** - * Provides an undefined distance. - * - * @return an undefined distance - */ @Override - public D undefinedDistance() { - return getDistanceFunction().getDistanceFactory().undefinedDistance(); + public Relation<? extends O> getRelation() { + return relation; } }
\ No newline at end of file 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 e619bc57..b9966b53 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,7 +27,6 @@ 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.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DBIDDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Run a distance query based on DBIDs @@ -36,14 +35,12 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * * @apiviz.landmark * @apiviz.uses DBIDDistanceFunction - * - * @param <D> Distance result type. */ -public class DBIDDistanceQuery<D extends Distance<D>> extends AbstractDatabaseDistanceQuery<DBID, D> { +public class DBIDDistanceQuery extends AbstractDatabaseDistanceQuery<DBID> { /** * The distance function we use. */ - final protected DBIDDistanceFunction<D> distanceFunction; + final protected DBIDDistanceFunction distanceFunction; /** * Constructor. @@ -51,13 +48,13 @@ public class DBIDDistanceQuery<D extends Distance<D>> extends AbstractDatabaseDi * @param relation Database to use. * @param distanceFunction Our distance function */ - public DBIDDistanceQuery(Relation<DBID> relation, DBIDDistanceFunction<D> distanceFunction) { + public DBIDDistanceQuery(Relation<DBID> relation, DBIDDistanceFunction distanceFunction) { super(relation); this.distanceFunction = distanceFunction; } @Override - public D distance(DBIDRef id1, DBIDRef id2) { + public double distance(DBIDRef id1, DBIDRef id2) { if(id1 == null) { throw new UnsupportedOperationException("This distance function can only be used for objects stored in the database."); } @@ -68,7 +65,7 @@ public class DBIDDistanceQuery<D extends Distance<D>> extends AbstractDatabaseDi } @Override - public DBIDDistanceFunction<D> getDistanceFunction() { + public DBIDDistanceFunction getDistanceFunction() { return distanceFunction; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDRangeDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDRangeDistanceQuery.java new file mode 100644 index 00000000..d5457dd5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDRangeDistanceQuery.java @@ -0,0 +1,74 @@ +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) 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.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; +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.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.DBIDDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.DBIDRangeDistanceFunction; + +/** + * Run a distance query based on DBIDRanges + * + * @author Erich Schubert + * + * @apiviz.landmark + * @apiviz.uses DBIDRangeDistanceFunction + */ +public class DBIDRangeDistanceQuery extends DBIDDistanceQuery { + /** + * The distance function we use. + */ + final protected DBIDRangeDistanceFunction distanceFunction; + + /** + * The DBID range we are accessing. + */ + final protected DBIDRange range; + + /** + * Constructor. + * + * @param relation Database to use. + * @param distanceFunction Our distance function + */ + public DBIDRangeDistanceQuery(Relation<DBID> relation, DBIDRangeDistanceFunction distanceFunction) { + super(relation, distanceFunction); + this.range = DBIDUtil.assertRange(relation.getDBIDs()); + this.distanceFunction = distanceFunction; + } + + @Override + public double distance(DBIDRef id1, DBIDRef id2) { + return distanceFunction.distance(range.getOffset(id1), range.getOffset(id2)); + } + + @Override + public DBIDDistanceFunction getDistanceFunction() { + return distanceFunction; + } +}
\ No newline at end of file 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 12e76ace..07bd6c53 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,20 +27,18 @@ 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.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** - * A distance query serves as adapter layer for database and primitive distances. + * A distance query serves as adapter layer for database and primitive + * distances. * * @author Erich Schubert * * @apiviz.landmark - * @apiviz.has Distance * * @param O Input object type - * @param D Distance result type */ -public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { +public interface DistanceQuery<O> extends DatabaseQuery { /** * Returns the distance between the two objects specified by their object ids. * @@ -48,7 +46,7 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param id2 second object id * @return the distance between the two objects specified by their object ids */ - D distance(DBIDRef id1, DBIDRef id2); + double distance(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -57,7 +55,7 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param id2 second object id * @return the distance between the two objects specified by their object ids */ - D distance(O o1, DBIDRef id2); + double distance(O o1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -66,7 +64,7 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param o2 second object * @return the distance between the two objects specified by their object ids */ - D distance(DBIDRef id1, O o2); + double distance(DBIDRef id1, O o2); /** * Returns the distance between the two objects specified by their object ids. @@ -75,44 +73,16 @@ public interface DistanceQuery<O, D extends Distance<?>> extends DatabaseQuery { * @param o2 second object * @return the distance between the two objects specified by their object ids */ - D distance(O o1, O o2); - - /** - * Method to get the distance functions factory. - * - * @return Factory for distance objects - */ - D getDistanceFactory(); + double distance(O o1, O o2); /** * Get the inner distance function. * * @return Distance function */ - DistanceFunction<? super O, D> getDistanceFunction(); - - /** - * Provides an infinite distance. - * - * @return an infinite distance - */ - D infiniteDistance(); + DistanceFunction<? super O> getDistanceFunction(); /** - * Provides a null distance. - * - * @return a null distance - */ - D nullDistance(); - - /** - * Provides an undefined distance. - * - * @return an undefined distance - */ - D undefinedDistance(); - - /** * Access the underlying data query. * * @return data query in use 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 ab3046ed..92125ae7 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.database.query.distance; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Run a database query in a database context. @@ -37,13 +36,12 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.uses PrimitiveDistanceFunction * * @param <O> Database object type. - * @param <D> Distance result type. */ -public class PrimitiveDistanceQuery<O, D extends Distance<D>> extends AbstractDistanceQuery<O, D> { +public class PrimitiveDistanceQuery<O> extends AbstractDistanceQuery<O> { /** * The distance function we use. */ - final protected PrimitiveDistanceFunction<? super O, D> distanceFunction; + final protected PrimitiveDistanceFunction<? super O> distanceFunction; /** * Constructor. @@ -51,32 +49,32 @@ public class PrimitiveDistanceQuery<O, D extends Distance<D>> extends AbstractDi * @param relation Representation to use. * @param distanceFunction Our distance function */ - public PrimitiveDistanceQuery(Relation<? extends O> relation, PrimitiveDistanceFunction<? super O, D> distanceFunction) { + public PrimitiveDistanceQuery(Relation<? extends O> relation, PrimitiveDistanceFunction<? super O> distanceFunction) { super(relation); this.distanceFunction = distanceFunction; } @Override - public D distance(DBIDRef id1, DBIDRef id2) { + public double distance(DBIDRef id1, DBIDRef id2) { O o1 = relation.get(id1); O o2 = relation.get(id2); return distance(o1, o2); } @Override - public D distance(O o1, DBIDRef id2) { + public double distance(O o1, DBIDRef id2) { O o2 = relation.get(id2); return distance(o1, o2); } @Override - public D distance(DBIDRef id1, O o2) { + public double distance(DBIDRef id1, O o2) { O o1 = relation.get(id1); return distance(o1, o2); } @Override - public D distance(O o1, O o2) { + public double distance(O o1, O o2) { if(o1 == null) { throw new UnsupportedOperationException("This distance function can only be used for object instances."); } @@ -87,7 +85,7 @@ public class PrimitiveDistanceQuery<O, D extends Distance<D>> extends AbstractDi } @Override - public PrimitiveDistanceFunction<? super O, D> getDistanceFunction() { + public PrimitiveDistanceFunction<? super O> getDistanceFunction() { return distanceFunction; } }
\ No newline at end of file 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 52f79f06..b90abc23 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,7 +27,6 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceSimilarityQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFunction; /** @@ -38,14 +37,13 @@ import de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFuncti * @apiviz.uses PrimitiveSimilarityFunction * * @param <O> Object type - * @param <D> Distance type */ -public class PrimitiveDistanceSimilarityQuery<O, D extends Distance<D>> extends PrimitiveDistanceQuery<O, D> implements DistanceSimilarityQuery<O, D> { +public class PrimitiveDistanceSimilarityQuery<O> extends PrimitiveDistanceQuery<O> implements DistanceSimilarityQuery<O> { /** * Typed reference to the similarity function (usually the same as the * distance function!) */ - private PrimitiveSimilarityFunction<? super O, D> similarityFunction; + private PrimitiveSimilarityFunction<? super O> similarityFunction; /** * Constructor. @@ -55,37 +53,37 @@ public class PrimitiveDistanceSimilarityQuery<O, D extends Distance<D>> extends * @param similarityFunction similarity function (usually the same as the * distance function!) */ - public PrimitiveDistanceSimilarityQuery(Relation<? extends O> relation, PrimitiveDistanceFunction<? super O, D> distanceFunction, PrimitiveSimilarityFunction<? super O, D> similarityFunction) { + public PrimitiveDistanceSimilarityQuery(Relation<? extends O> relation, PrimitiveDistanceFunction<? super O> distanceFunction, PrimitiveSimilarityFunction<? super O> similarityFunction) { super(relation, distanceFunction); this.similarityFunction = similarityFunction; } @Override - public D similarity(DBIDRef id1, DBIDRef id2) { + public double similarity(DBIDRef id1, DBIDRef id2) { O o1 = relation.get(id1); O o2 = relation.get(id2); return similarity(o1, o2); } @Override - public D similarity(O o1, DBIDRef id2) { + public double similarity(O o1, DBIDRef id2) { O o2 = relation.get(id2); return similarity(o1, o2); } @Override - public D similarity(DBIDRef id1, O o2) { + public double similarity(DBIDRef id1, O o2) { O o1 = relation.get(id1); return similarity(o1, o2); } @Override - public D similarity(O o1, O o2) { + public double similarity(O o1, O o2) { return this.similarityFunction.similarity(o1, o2); } @Override - public PrimitiveSimilarityFunction<? super O, D> getSimilarityFunction() { + public PrimitiveSimilarityFunction<? super O> getSimilarityFunction() { return similarityFunction; } } 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 14839dd7..1340130e 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.database.query.distance; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Query interface for spatial distance queries. @@ -34,9 +33,8 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @param <V> Vector type - * @param <D> Distance type */ -public interface SpatialDistanceQuery<V extends SpatialComparable, D extends Distance<D>> extends DistanceQuery<V, D> { +public interface SpatialDistanceQuery<V extends SpatialComparable> extends DistanceQuery<V> { /** * Computes the minimum distance between the given MBR and the FeatureVector * object according to this distance function. @@ -46,7 +44,7 @@ public interface SpatialDistanceQuery<V extends SpatialComparable, D extends Dis * @return the minimum distance between the given MBR and the FeatureVector * object according to this distance function */ - D minDist(SpatialComparable mbr, V v); + double minDist(SpatialComparable mbr, V v); /** * Computes the minimum distance between the given MBR and the FeatureVector @@ -57,7 +55,7 @@ public interface SpatialDistanceQuery<V extends SpatialComparable, D extends Dis * @return the minimum distance between the given MBR and the FeatureVector * object according to this distance function */ - D minDist(SpatialComparable mbr, DBID id); + double minDist(SpatialComparable mbr, DBID id); /** * Get the inner distance function. @@ -65,5 +63,5 @@ public interface SpatialDistanceQuery<V extends SpatialComparable, D extends Dis * @return Distance function */ @Override - SpatialPrimitiveDistanceFunction<? super V, D> getDistanceFunction(); + SpatialPrimitiveDistanceFunction<? super V> getDistanceFunction(); }
\ No newline at end of file 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 c5a601bd..4453a2ef 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,7 +27,6 @@ import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Distance query for spatial distance functions @@ -36,35 +35,34 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.uses SpatialPrimitiveDistanceFunction * * @param <V> Vector type to use - * @param <D> Distance result type */ -public class SpatialPrimitiveDistanceQuery<V extends SpatialComparable, D extends Distance<D>> extends PrimitiveDistanceQuery<V, D> implements SpatialDistanceQuery<V, D> { +public class SpatialPrimitiveDistanceQuery<V extends SpatialComparable> extends PrimitiveDistanceQuery<V> implements SpatialDistanceQuery<V> { /** * The distance function we use. */ - final protected SpatialPrimitiveDistanceFunction<? super V, D> distanceFunction; + final protected SpatialPrimitiveDistanceFunction<? super V> distanceFunction; /** * @param relation Representation to use * @param distanceFunction Distance function to use */ - public SpatialPrimitiveDistanceQuery(Relation<? extends V> relation, SpatialPrimitiveDistanceFunction<? super V, D> distanceFunction) { + public SpatialPrimitiveDistanceQuery(Relation<? extends V> relation, SpatialPrimitiveDistanceFunction<? super V> distanceFunction) { super(relation, distanceFunction); this.distanceFunction = distanceFunction; } @Override - public D minDist(SpatialComparable mbr, V v) { + public double minDist(SpatialComparable mbr, V v) { return distanceFunction.minDist(mbr, v); } @Override - public D minDist(SpatialComparable mbr, DBID id) { + public double minDist(SpatialComparable mbr, DBID id) { return distanceFunction.minDist(mbr, relation.get(id)); } @Override - public SpatialPrimitiveDistanceFunction<? super V, D> getDistanceFunction() { + public SpatialPrimitiveDistanceFunction<? super V> getDistanceFunction() { return distanceFunction; } }
\ 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 97bc471d..0d949669 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 @@ -2,12 +2,13 @@ * <p>Prepared queries for distances.</p> * * @apiviz.exclude .*Instance + * @apiviz.exclude de.lmu.ifi.dbs.elki.index.distance.* */ /* 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 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 f9f7d018..8d0d574f 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,49 +29,54 @@ import java.util.List; 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.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; 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; /** * Instance for the query on a particular database. * * @author Erich Schubert */ -public abstract class AbstractDistanceKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { +public abstract class AbstractDistanceKNNQuery<O> implements KNNQuery<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 used */ - public AbstractDistanceKNNQuery(DistanceQuery<O, D> distanceQuery) { - super(distanceQuery.getRelation()); + public AbstractDistanceKNNQuery(DistanceQuery<O> distanceQuery) { + super(); + this.relation = distanceQuery.getRelation(); this.distanceQuery = distanceQuery; } @Override - public List<? extends KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<? extends KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { // throw new // UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); // TODO: optimize - List<KNNList<D>> ret = new ArrayList<>(ids.size()); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + List<KNNList> ret = new ArrayList<>(ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { ret.add(getKNNForDBID(iter, k)); } return ret; } @Override - public KNNList<D> getKNNForDBID(DBIDRef id, int k) { + public KNNList getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @Override - abstract public KNNList<D> getKNNForObject(O obj, int k); + abstract public KNNList getKNNForObject(O obj, int k); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/DoubleOptimizedDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/DoubleOptimizedDistanceKNNQuery.java deleted file mode 100644 index 4391b745..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/DoubleOptimizedDistanceKNNQuery.java +++ /dev/null @@ -1,91 +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) 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.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.ids.distance.DoubleDistanceKNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList; -import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; -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.PrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Optimized linear scan query for {@link PrimitiveDoubleDistanceFunction}s. - * - * @author Erich Schubert - * - * @apiviz.uses PrimitiveDoubleDistanceFunction - * - * @param <O> Object type - */ -public class DoubleOptimizedDistanceKNNQuery<O> extends AbstractDistanceKNNQuery<O, DoubleDistance> implements LinearScanQuery { - /** - * Raw distance function. - */ - PrimitiveDoubleDistanceFunction<O> rawdist; - - /** - * Constructor.newDoubleDistanceHeap - * - * @param distanceQuery Distance function to use - */ - @SuppressWarnings("unchecked") - public DoubleOptimizedDistanceKNNQuery(PrimitiveDistanceQuery<O, DoubleDistance> distanceQuery) { - super(distanceQuery); - if(!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { - throw new UnsupportedOperationException("DoubleOptimizedKNNQuery instantiated for non-PrimitiveDoubleDistanceFunction!"); - } - rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); - } - - @Override - public DoubleDistanceKNNList getKNNForDBID(DBIDRef id, int k) { - final Relation<? extends O> relation = this.relation; - DoubleDistanceKNNHeap heap = DBIDFactory.FACTORY.newDoubleDistanceHeap(k); - linearScan(relation, relation.iterDBIDs(), rawdist, relation.get(id), heap); - return heap.toKNNList(); - } - - @Override - public DoubleDistanceKNNList getKNNForObject(O obj, int k) { - DoubleDistanceKNNHeap heap = DBIDFactory.FACTORY.newDoubleDistanceHeap(k); - linearScan(relation, relation.iterDBIDs(), rawdist, obj, heap); - return heap.toKNNList(); - } - - private static <O> void linearScan(Relation<? extends O> relation, DBIDIter iter, PrimitiveDoubleDistanceFunction<? super O> rawdist, final O obj, DoubleDistanceKNNHeap heap) { - double kdist = Double.POSITIVE_INFINITY; - while(iter.valid()) { - final double dist = rawdist.doubleDistance(obj, relation.get(iter)); - if(dist <= kdist) { - kdist = heap.insert(dist, iter); - } - iter.advance(); - } - } -} 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 c94f3d42..1798ea0b 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,9 +27,8 @@ 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.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * The interface of an actual instance. @@ -40,9 +39,8 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.has KNNList oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { +public interface KNNQuery<O> extends DatabaseQuery { /** * Get the k nearest neighbors for a particular id. * @@ -50,7 +48,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public KNNList<D> getKNNForDBID(DBIDRef id, int k); + public KNNList getKNNForDBID(DBIDRef id, int k); /** * Bulk query method @@ -59,7 +57,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<? extends KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); + public List<? extends KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); /** * Get the k nearest neighbors for a particular id. @@ -68,5 +66,5 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public KNNList<D> getKNNForObject(O obj, int k); + public KNNList getKNNForObject(O obj, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanDistanceKNNQuery.java index 395db289..06e8ca00 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanDistanceKNNQuery.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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,12 +30,10 @@ 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.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Instance of this query for a particular database. @@ -45,76 +43,73 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.landmark * @apiviz.has DistanceQuery */ -public class LinearScanDistanceKNNQuery<O, D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> implements LinearScanQuery { +public class LinearScanDistanceKNNQuery<O> extends AbstractDistanceKNNQuery<O> implements LinearScanQuery { /** * Constructor. * * @param distanceQuery Distance function to use */ - public LinearScanDistanceKNNQuery(DistanceQuery<O, D> distanceQuery) { + public LinearScanDistanceKNNQuery(DistanceQuery<O> distanceQuery) { super(distanceQuery); } - /** - * Linear batch knn for arbitrary distance functions. - * - * @param ids DBIDs to process - * @param heaps Heaps to store the results in - */ - private void linearScanBatchKNN(ArrayDBIDs ids, List<KNNHeap<D>> heaps) { - // The distance is computed on database IDs + @Override + public KNNList getKNNForDBID(DBIDRef id, int k) { + KNNHeap heap = DBIDUtil.newHeap(k); + double max = Double.POSITIVE_INFINITY; for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - int index = 0; - for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { - KNNHeap<D> heap = heaps.get(index); - heap.insert(distanceQuery.distance(iter2, iter), iter); - index++; + final double dist = distanceQuery.distance(id, iter); + if(dist <= max) { + max = heap.insert(dist, iter); } } + return heap.toKNNList(); } @Override - public KNNList<D> getKNNForDBID(DBIDRef id, int k) { - if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) { - // This should have yielded a LinearScanPrimitiveDistanceKNNQuery class! - return getKNNForObject(relation.get(id), k); - } - KNNHeap<D> heap = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k); - D max = distanceQuery.getDistanceFactory().infiniteDistance(); + public KNNList getKNNForObject(O obj, int k) { + KNNHeap heap = DBIDUtil.newHeap(k); + double max = Double.POSITIVE_INFINITY; for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - final D dist = distanceQuery.distance(id, iter); - if(max.compareTo(dist) > 0) { - heap.insert(dist, iter); - if(heap.size() >= k) { - max = heap.getKNNDistance(); - } + final double dist = distanceQuery.distance(obj, iter); + if(dist <= max) { + max = heap.insert(dist, iter); } } return heap.toKNNList(); } @Override - public List<KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { final int size = ids.size(); - final List<KNNHeap<D>> heaps = new ArrayList<>(size); + final List<KNNHeap> heaps = new ArrayList<>(size); for(int i = 0; i < size; i++) { - heaps.add(DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k)); + heaps.add(DBIDUtil.newHeap(k)); } linearScanBatchKNN(ids, heaps); // Serialize heaps - List<KNNList<D>> result = new ArrayList<>(size); - for(KNNHeap<D> heap : heaps) { + List<KNNList> result = new ArrayList<>(size); + for(KNNHeap heap : heaps) { result.add(heap.toKNNList()); } return result; } - @Override - public KNNList<D> getKNNForObject(O obj, int k) { - KNNHeap<D> heap = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k); + /** + * Linear batch knn for arbitrary distance functions. + * + * @param ids DBIDs to process + * @param heaps Heaps to store the results in + */ + private void linearScanBatchKNN(ArrayDBIDs ids, List<KNNHeap> heaps) { + // The distance is computed on database IDs for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.insert(distanceQuery.distance(obj, iter), iter); + int index = 0; + for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + KNNHeap heap = heaps.get(index); + heap.insert(distanceQuery.distance(iter2, iter), iter); + index++; + } } - return heap.toKNNList(); } } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanEuclideanDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanEuclideanDistanceKNNQuery.java new file mode 100644 index 00000000..36d739ac --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanEuclideanDistanceKNNQuery.java @@ -0,0 +1,141 @@ +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) 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 java.util.ArrayList; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.QueryUtil; +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.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; +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.EuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; + +/** + * Instance of this query for a particular database. + * + * This is a subtle optimization: for primitive queries, it is clearly faster to + * retrieve the query object from the relation only once! + * + * @author Erich Schubert + * + * @apiviz.uses PrimitiveDistanceQuery + * @apiviz.uses EuclideanDistanceFunction + * @apiviz.uses SquaredEuclideanDistanceFunction + */ +public class LinearScanEuclideanDistanceKNNQuery<O extends NumberVector> extends LinearScanPrimitiveDistanceKNNQuery<O> implements LinearScanQuery { + /** + * Squared Euclidean distance function. + */ + private static final SquaredEuclideanDistanceFunction SQUARED = SquaredEuclideanDistanceFunction.STATIC; + + /** + * Constructor. + * + * @param distanceQuery Distance function to use + */ + public LinearScanEuclideanDistanceKNNQuery(PrimitiveDistanceQuery<O> distanceQuery) { + super(distanceQuery); + assert (EuclideanDistanceFunction.STATIC.equals(distanceQuery.getDistanceFunction())); + } + + @Override + public KNNList getKNNForDBID(DBIDRef id, int k) { + return QueryUtil.applySqrt(linearScan(relation, relation.iterDBIDs(), relation.get(id), DBIDUtil.newHeap(k)).toKNNList()); + } + + @Override + public KNNList getKNNForObject(O obj, int k) { + return QueryUtil.applySqrt(linearScan(relation, relation.iterDBIDs(), obj, DBIDUtil.newHeap(k)).toKNNList()); + } + + /** + * Main loop of the linear scan. + * + * @param relation Data relation + * @param iter ID iterator + * @param obj Query object + * @param heap Output heap + * @return Heap + */ + private KNNHeap linearScan(Relation<? extends O> relation, DBIDIter iter, final O obj, KNNHeap heap) { + double max = Double.POSITIVE_INFINITY; + while(iter.valid()) { + final double dist = SQUARED.distance(obj, relation.get(iter)); + if(dist <= max) { + max = heap.insert(dist, iter); + } + iter.advance(); + } + return heap; + } + + @Override + public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + final int size = ids.size(); + final List<KNNHeap> heaps = new ArrayList<>(size); + List<O> objs = new ArrayList<>(size); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + heaps.add(DBIDUtil.newHeap(k)); + objs.add(relation.get(iter)); + } + linearScanBatchKNN(objs, heaps); + + List<KNNList> result = new ArrayList<>(heaps.size()); + for(KNNHeap heap : heaps) { + result.add(QueryUtil.applySqrt(heap.toKNNList())); + } + return result; + } + + /** + * Perform a linear scan batch kNN for primitive distance functions. + * + * @param objs Objects list + * @param heaps Heaps array + */ + @Override + protected void linearScanBatchKNN(List<O> objs, List<KNNHeap> heaps) { + final int size = objs.size(); + // Linear scan style KNN. + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + O candidate = relation.get(iter); + for(int index = 0; index < size; index++) { + final KNNHeap heap = heaps.get(index); + final double dist = SQUARED.distance(objs.get(index), candidate); + if(dist <= heap.getKNNDistance()) { + heap.insert(dist, iter); + } + } + } + } +}
\ 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 59a6d6e3..20a120e5 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,11 +30,12 @@ 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.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; 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; /** * Instance of this query for a particular database. @@ -45,69 +46,91 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @apiviz.uses PrimitiveDistanceQuery + * @apiviz.uses PrimitiveDistanceFunction */ -public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> implements LinearScanQuery { +public class LinearScanPrimitiveDistanceKNNQuery<O> extends AbstractDistanceKNNQuery<O> implements LinearScanQuery { + /** + * Unboxed distance function. + */ + private PrimitiveDistanceFunction<? super O> rawdist; + /** * Constructor. * * @param distanceQuery Distance function to use */ - public LinearScanPrimitiveDistanceKNNQuery(PrimitiveDistanceQuery<O, D> distanceQuery) { + public LinearScanPrimitiveDistanceKNNQuery(PrimitiveDistanceQuery<O> distanceQuery) { super(distanceQuery); + rawdist = distanceQuery.getDistanceFunction(); } - /** - * Perform a linear scan batch kNN for primitive distance functions. - * - * @param objs Objects list - * @param heaps Heaps array - */ - protected void linearScanBatchKNN(List<O> objs, List<KNNHeap<D>> heaps) { - final int size = objs.size(); - // Linear scan style KNN. - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - O candidate = relation.get(iter); - for(int index = 0; index < size; index++) { - O object = objs.get(index); - heaps.get(index).insert(distanceQuery.distance(object, candidate), iter); - } - } + @Override + public KNNList getKNNForDBID(DBIDRef id, int k) { + return linearScan(relation, relation.iterDBIDs(), relation.get(id), DBIDUtil.newHeap(k)).toKNNList(); } @Override - public KNNList<D> getKNNForDBID(DBIDRef id, int k) { - final O obj = relation.get(id); - KNNHeap<D> heap = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k); - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.insert(distanceQuery.distance(obj, iter), iter); - } - return heap.toKNNList(); + public KNNList getKNNForObject(O obj, int k) { + return linearScan(relation, relation.iterDBIDs(), obj, DBIDUtil.newHeap(k)).toKNNList(); } - @Override - public KNNList<D> getKNNForObject(O obj, int k) { - KNNHeap<D> heap = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k); - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.insert(distanceQuery.distance(obj, iter), iter); + /** + * Main loop of the linear scan. + * + * @param relation Data relation + * @param iter ID iterator + * @param obj Query object + * @param heap Output heap + * @return Heap + */ + private KNNHeap linearScan(Relation<? extends O> relation, DBIDIter iter, final O obj, KNNHeap heap) { + double max = Double.POSITIVE_INFINITY; + while(iter.valid()) { + final double dist = rawdist.distance(obj, relation.get(iter)); + if(dist <= max) { + max = heap.insert(dist, iter); + } + iter.advance(); } - return heap.toKNNList(); + return heap; } @Override - public List<KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { final int size = ids.size(); - final List<KNNHeap<D>> heaps = new ArrayList<>(size); + final List<KNNHeap> heaps = new ArrayList<>(size); List<O> objs = new ArrayList<>(size); for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - heaps.add(DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k)); + heaps.add(DBIDUtil.newHeap(k)); objs.add(relation.get(iter)); } linearScanBatchKNN(objs, heaps); - List<KNNList<D>> result = new ArrayList<>(heaps.size()); - for(KNNHeap<D> heap : heaps) { + List<KNNList> result = new ArrayList<>(heaps.size()); + for(KNNHeap heap : heaps) { result.add(heap.toKNNList()); } return result; } + + /** + * Perform a linear scan batch kNN for primitive distance functions. + * + * @param objs Objects list + * @param heaps Heaps array + */ + protected void linearScanBatchKNN(List<O> objs, List<KNNHeap> heaps) { + final int size = objs.size(); + // Linear scan style KNN. + for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + O candidate = relation.get(iter); + for(int index = 0; index < size; index++) { + final KNNHeap heap = heaps.get(index); + final double dist = rawdist.distance(objs.get(index), candidate); + if(dist <= heap.getKNNDistance()) { + heap.insert(dist, iter); + } + } + } + } }
\ 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 0f555c79..2f51c998 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,10 +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.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; 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.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -42,12 +40,19 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * Instance for a particular database, invoking the preprocessor. * * @author Erich Schubert + * + * @param <O> Data object type */ -public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNList<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { +public class PreprocessorKNNQuery<O> implements KNNQuery<O> { + /** + * The data to use for this query + */ + final protected Relation<? extends O> relation; + /** * The last preprocessor result */ - final private AbstractMaterializeKNNPreprocessor<O, D, T> preprocessor; + final private AbstractMaterializeKNNPreprocessor<O> preprocessor; /** * Warn only once. @@ -57,36 +62,27 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNList<D> /** * Constructor. * - * @param database Database to query + * @param relation Relation to query * @param preprocessor Preprocessor instance to use */ - public PreprocessorKNNQuery(Relation<O> database, AbstractMaterializeKNNPreprocessor<O, D, T> preprocessor) { - super(database); + public PreprocessorKNNQuery(Relation<O> relation, AbstractMaterializeKNNPreprocessor<O> preprocessor) { + super(); + this.relation = relation; this.preprocessor = preprocessor; } - /** - * Constructor. - * - * @param database Database to query - * @param preprocessor Preprocessor to use - */ - public PreprocessorKNNQuery(Relation<O> database, AbstractMaterializeKNNPreprocessor.Factory<O, D, T> preprocessor) { - this(database, preprocessor.instantiate(database)); - } - @Override - public KNNList<D> getKNNForDBID(DBIDRef id, int k) { + public KNNList getKNNForDBID(DBIDRef id, int k) { if(!warned && k > preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } if(!warned && k < preprocessor.getK()) { - KNNList<D> dr = preprocessor.get(id); + KNNList dr = preprocessor.get(id); int subk = k; - D kdist = dr.get(subk - 1).getDistance(); + double kdist = dr.get(subk - 1).doubleValue(); while(subk < dr.size()) { - D ndist = dr.get(subk).getDistance(); - if(kdist.equals(ndist)) { + double ndist = dr.get(subk).doubleValue(); + if(kdist == ndist) { // Tie - increase subk. subk++; } @@ -105,19 +101,19 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNList<D> } @Override - public List<KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(!warned && k > preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } - List<KNNList<D>> result = new ArrayList<>(ids.size()); + List<KNNList> result = new ArrayList<>(ids.size()); if(k < preprocessor.getK()) { - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - KNNList<D> dr = preprocessor.get(iter); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + KNNList dr = preprocessor.get(iter); int subk = k; - D kdist = dr.get(subk - 1).getDistance(); + double kdist = dr.get(subk - 1).doubleValue(); while(subk < dr.size()) { - D ndist = dr.get(subk).getDistance(); - if(kdist.equals(ndist)) { + double ndist = dr.get(subk).doubleValue(); + if(kdist == ndist) { // Tie - increase subk. subk++; } @@ -134,7 +130,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNList<D> } } else { - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { result.add(preprocessor.get(iter)); } } @@ -142,7 +138,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNList<D> } @Override - public KNNList<D> getKNNForObject(O obj, int k) { + public KNNList getKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @@ -151,7 +147,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNList<D> * * @return preprocessor instance */ - public AbstractMaterializeKNNPreprocessor<O, D, T> getPreprocessor() { + public AbstractMaterializeKNNPreprocessor<O> getPreprocessor() { return preprocessor; } }
\ 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 17d8e4b0..31ecd704 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 @@ -8,7 +8,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 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 fb3539bc..bf4b4be9 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 @@ -81,7 +81,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 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 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 8a88bf0f..5036ae43 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,32 +24,37 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; */ 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; /** * Instance for the query on a particular database. * * @author Erich Schubert */ -public abstract class AbstractRKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements RKNNQuery<O, D> { +public abstract class AbstractRKNNQuery<O> implements RKNNQuery<O> { + /** + * The data to use for this query + */ + final protected Relation<? extends O> relation; + /** * Hold the distance function to be used. */ - protected final DistanceQuery<O, D> distanceQuery; + final protected DistanceQuery<O> distanceQuery; /** * Constructor. * * @param distanceQuery distance query */ - public AbstractRKNNQuery(DistanceQuery<O, D> distanceQuery) { - super(distanceQuery.getRelation()); + public AbstractRKNNQuery(DistanceQuery<O> distanceQuery) { + super(); + this.relation = distanceQuery.getRelation(); this.distanceQuery = distanceQuery; } @Override - abstract public DistanceDBIDList<D> getRKNNForDBID(DBIDRef id, int k); + abstract public DoubleDBIDList 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 71cf0619..3d55c3a6 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,14 +30,13 @@ 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.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +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.database.query.knn.KNNQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Default linear scan RKNN query class. @@ -48,14 +47,13 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @apiviz.has KNNQuery * * @param <O> Database object type - * @param <D> Distance type */ // FIXME: Validate this works correctly. -public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQuery<O, D> implements LinearScanQuery { +public class LinearScanRKNNQuery<O> extends AbstractRKNNQuery<O> implements LinearScanQuery { /** * KNN query we use. */ - protected final KNNQuery<O, D> knnQuery; + protected final KNNQuery<O> knnQuery; /** * Constructor. @@ -64,24 +62,24 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ * @param knnQuery kNN query to use. * @param maxk k to use */ - public LinearScanRKNNQuery(DistanceQuery<O, D> distanceQuery, KNNQuery<O, D> knnQuery, Integer maxk) { + public LinearScanRKNNQuery(DistanceQuery<O> distanceQuery, KNNQuery<O> knnQuery, Integer maxk) { super(distanceQuery); this.knnQuery = knnQuery; } @Override - public DistanceDBIDList<D> getRKNNForObject(O obj, int k) { - GenericDistanceDBIDList<D> rNNlist = new GenericDistanceDBIDList<>(); + public DoubleDBIDList getRKNNForObject(O obj, int k) { + ModifiableDoubleDBIDList rNNlist = DBIDUtil.newDistanceDBIDList(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<? extends KNNList<D>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNList> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; - for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { - KNNList<D> knn = kNNLists.get(i); + for(DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { + KNNList knn = kNNLists.get(i); 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) { + double dist = distanceQuery.distance(obj, iter); + if(last < k - 1 || dist <= knn.get(last).doubleValue()) { rNNlist.add(dist, iter); } i++; @@ -91,18 +89,18 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } @Override - public DistanceDBIDList<D> getRKNNForDBID(DBIDRef id, int k) { - GenericDistanceDBIDList<D> rNNList = new GenericDistanceDBIDList<>(); - + public DoubleDBIDList getRKNNForDBID(DBIDRef id, int k) { + ModifiableDoubleDBIDList rNNList = DBIDUtil.newDistanceDBIDList(); + ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<? extends KNNList<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNList> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; - for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { - KNNList<D> knn = kNNList.get(i); - for(DistanceDBIDListIter<D> n = knn.iter(); n.valid(); n.advance()) { + for(DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { + KNNList knn = kNNList.get(i); + for(DoubleDBIDListIter n = knn.iter(); n.valid(); n.advance()) { if(DBIDUtil.equal(n, id)) { - rNNList.add(n.getDistance(), iter); + rNNList.add(n.doubleValue(), iter); } } i++; @@ -112,24 +110,24 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } @Override - public List<GenericDistanceDBIDList<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { - List<GenericDistanceDBIDList<D>> rNNList = new ArrayList<>(ids.size()); + public List<? extends DoubleDBIDList> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + List<ModifiableDoubleDBIDList> rNNList = new ArrayList<>(ids.size()); for(int i = 0; i < ids.size(); i++) { - rNNList.add(new GenericDistanceDBIDList<D>()); + rNNList.add(DBIDUtil.newDistanceDBIDList()); } ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<? extends KNNList<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNList> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; - for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { - KNNList<D> knn = kNNList.get(i); - for(DistanceDBIDListIter<D> n = knn.iter(); n.valid(); n.advance()) { + for(DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { + KNNList knn = kNNList.get(i); + for(DoubleDBIDListIter n = knn.iter(); n.valid(); n.advance()) { int j = 0; - for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { if(DBIDUtil.equal(n, iter2)) { - GenericDistanceDBIDList<D> rNN = rNNList.get(j); - rNN.add(n.getDistance(), iter); + ModifiableDoubleDBIDList rNN = rNNList.get(j); + rNN.add(n.doubleValue(), iter); } j++; } 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 9f8f9c71..d18b2c21 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,10 +29,8 @@ import java.util.List; 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.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.relation.Relation; -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; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -42,11 +40,16 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @author Elke Achtert */ -public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements RKNNQuery<O, D> { +public class PreprocessorRKNNQuery<O> implements RKNNQuery<O> { + /** + * The data to use for this query + */ + final protected Relation<? extends O> relation; + /** * The last preprocessor result */ - final private MaterializeKNNAndRKNNPreprocessor<O, D> preprocessor; + final private MaterializeKNNAndRKNNPreprocessor<O> preprocessor; /** * Warn only once. @@ -56,11 +59,12 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat /** * Constructor. * - * @param database Database to query + * @param relation Relation to query * @param preprocessor Preprocessor instance to use */ - public PreprocessorRKNNQuery(Relation<O> database, MaterializeKNNAndRKNNPreprocessor<O, D> preprocessor) { - super(database); + public PreprocessorRKNNQuery(Relation<O> relation, MaterializeKNNAndRKNNPreprocessor<O> preprocessor) { + super(); + this.relation = relation; this.preprocessor = preprocessor; } @@ -70,30 +74,30 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat * @param database Database to query * @param preprocessor Preprocessor to use */ - public PreprocessorRKNNQuery(Relation<O> database, MaterializeKNNAndRKNNPreprocessor.Factory<O, D> preprocessor) { + public PreprocessorRKNNQuery(Relation<O> database, MaterializeKNNAndRKNNPreprocessor.Factory<O> preprocessor) { this(database, preprocessor.instantiate(database)); } @Override - public DistanceDBIDList<D> getRKNNForDBID(DBIDRef id, int k) { + public DoubleDBIDList getRKNNForDBID(DBIDRef id, int k) { if(!warned && k != preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } return preprocessor.getRKNN(id); } - + @Override - public DistanceDBIDList<D> getRKNNForObject(O obj, int k) { + public DoubleDBIDList getRKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } - + @Override - public List<? extends DistanceDBIDList<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<? extends DoubleDBIDList> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(!warned && k != preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } - List<DistanceDBIDList<D>> result = new ArrayList<>(ids.size()); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + List<DoubleDBIDList> result = new ArrayList<>(ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { 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 0a05d797..97ea76be 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,21 +27,19 @@ 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.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; /** * Abstract reverse kNN Query interface. * * @author Erich Schubert * - * @apiviz.uses DistanceDBIDList oneway - - «create» + * @apiviz.uses DoubleDBIDList oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { +public interface RKNNQuery<O> extends DatabaseQuery { /** * Get the reverse k nearest neighbors for a particular id. * @@ -49,7 +47,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public DistanceDBIDList<D> getRKNNForDBID(DBIDRef id, int k); + public DoubleDBIDList getRKNNForDBID(DBIDRef id, int k); /** * Get the reverse k nearest neighbors for a particular object. @@ -58,7 +56,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public DistanceDBIDList<D> getRKNNForObject(O obj, int k); + public DoubleDBIDList getRKNNForObject(O obj, int k); /** * Bulk query method for reverse k nearest neighbors for ids. @@ -67,5 +65,5 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<? extends DistanceDBIDList<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); + public List<? extends DoubleDBIDList> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); }
\ 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 8c0501b6..9ab02433 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) 2013 +Copyright (C) 2014 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 8dc6dd61..b7a8c5af 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,7 +25,6 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * Run a database query in a database context. @@ -33,9 +32,8 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * @author Erich Schubert * * @param <O> Database object type. - * @param <D> Distance result type. */ -public abstract class AbstractDBIDSimilarityQuery<O, D extends Distance<D>> extends AbstractSimilarityQuery<O, D> { +public abstract class AbstractDBIDSimilarityQuery<O> extends AbstractSimilarityQuery<O> { /** * Constructor. * @@ -46,17 +44,17 @@ public abstract class AbstractDBIDSimilarityQuery<O, D extends Distance<D>> exte } @Override - public D similarity(O o1, DBIDRef id2) { + public double similarity(O o1, DBIDRef id2) { throw new UnsupportedOperationException("This distance function can only be used for objects when referenced by ID."); } @Override - public D similarity(DBIDRef id1, O o2) { + public double similarity(DBIDRef id1, O o2) { throw new UnsupportedOperationException("This distance function can only be used for objects when referenced by ID."); } @Override - public D similarity(O o1, O o2) { + public double similarity(O o1, O o2) { throw new UnsupportedOperationException("This distance function can only be used for objects when referenced by ID."); } }
\ No newline at end of file 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 fbcf76a7..99cce405 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,9 +24,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; */ 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.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** * A distance query serves as adapter layer for database and primitive @@ -34,17 +32,22 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * * @author Erich Schubert * - * @param O Input object type - * @param D Distance result type + * @param <O> Input object type */ -public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements SimilarityQuery<O, D> { +public abstract class AbstractSimilarityQuery<O> implements SimilarityQuery<O> { + /** + * The data to use for this query + */ + final protected Relation<? extends O> relation; + /** * Constructor. * * @param relation Relation to use. */ public AbstractSimilarityQuery(Relation<? extends O> relation) { - super(relation); + super(); + this.relation = relation; } /** @@ -55,7 +58,7 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(DBIDRef id1, DBIDRef id2); + public abstract double similarity(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -65,7 +68,7 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(O o1, DBIDRef id2); + public abstract double similarity(O o1, DBIDRef id2); /** * Returns the distance between the two objects specified by their object ids. @@ -75,7 +78,7 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(DBIDRef id1, O o2); + public abstract double similarity(DBIDRef id1, O o2); /** * Returns the distance between the two objects specified by their object ids. @@ -85,5 +88,10 @@ public abstract class AbstractSimilarityQuery<O, D extends Distance<D>> extends * @return the distance between the two objects specified by their object ids */ @Override - public abstract D similarity(O o1, O o2); + public abstract double similarity(O o1, O o2); + + @Override + public Relation<? extends O> getRelation() { + return relation; + } }
\ No newline at end of file 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 58020239..f39383a2 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,7 +25,6 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFunction; /** @@ -33,14 +32,15 @@ import de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFuncti * * @author Erich Schubert * + * @apiviz.has PrimitiveSimilarityFunction + * * @param <O> Database object type. - * @param <D> Distance result type. */ -public class PrimitiveSimilarityQuery<O, D extends Distance<D>> extends AbstractSimilarityQuery<O, D> { +public class PrimitiveSimilarityQuery<O> extends AbstractSimilarityQuery<O> { /** * The distance function we use. */ - final protected PrimitiveSimilarityFunction<? super O, D> similarityFunction; + final protected PrimitiveSimilarityFunction<? super O> similarityFunction; /** * Constructor. @@ -48,48 +48,33 @@ public class PrimitiveSimilarityQuery<O, D extends Distance<D>> extends Abstract * @param relation Relation to use. * @param similarityFunction Our similarity function */ - public PrimitiveSimilarityQuery(Relation<? extends O> relation, PrimitiveSimilarityFunction<? super O, D> similarityFunction) { + public PrimitiveSimilarityQuery(Relation<? extends O> relation, PrimitiveSimilarityFunction<? super O> similarityFunction) { super(relation); this.similarityFunction = similarityFunction; } @Override - public D similarity(DBIDRef id1, DBIDRef id2) { - O o1 = relation.get(id1); - O o2 = relation.get(id2); - return similarity(o1, o2); + public double similarity(DBIDRef id1, DBIDRef id2) { + return similarity(relation.get(id1), relation.get(id2)); } @Override - public D similarity(O o1, DBIDRef id2) { - O o2 = relation.get(id2); - return similarity(o1, o2); + public double similarity(O o1, DBIDRef id2) { + return similarity(o1, relation.get(id2)); } @Override - public D similarity(DBIDRef id1, O o2) { - O o1 = relation.get(id1); - return similarity(o1, o2); + public double similarity(DBIDRef id1, O o2) { + return similarity(relation.get(id1), o2); } @Override - public D similarity(O o1, O o2) { - if (o1 == null) { - throw new UnsupportedOperationException("This distance function can only be used for object instances."); - } - if (o2 == null) { - throw new UnsupportedOperationException("This distance function can only be used for object instances."); - } + public double similarity(O o1, O o2) { return similarityFunction.similarity(o1, o2); } @Override - public D getDistanceFactory() { - return similarityFunction.getDistanceFactory(); - } - - @Override - public PrimitiveSimilarityFunction<? super O, D> getSimilarityFunction() { + public PrimitiveSimilarityFunction<? super O> getSimilarityFunction() { return similarityFunction; } } 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 80347fb7..2b835437 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.distance.similarityfunction.SimilarityFunction; /** @@ -36,12 +35,10 @@ import de.lmu.ifi.dbs.elki.distance.similarityfunction.SimilarityFunction; * @author Erich Schubert * * @apiviz.landmark - * @apiviz.has Distance * - * @param O Input object type - * @param D Distance result type + * @param <O> Input object type */ -public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery { +public interface SimilarityQuery<O> extends DatabaseQuery { /** * Returns the similarity between the two objects specified by their object * ids. @@ -51,7 +48,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - D similarity(DBIDRef id1, DBIDRef id2); + double similarity(DBIDRef id1, DBIDRef id2); /** * Returns the similarity between the two objects specified by their object @@ -62,7 +59,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - D similarity(O o1, DBIDRef id2); + double similarity(O o1, DBIDRef id2); /** * Returns the similarity between the two objects specified by their object @@ -73,7 +70,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - D similarity(DBIDRef id1, O o2); + double similarity(DBIDRef id1, O o2); /** * Returns the similarity between the two objects specified by their object @@ -84,14 +81,7 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * @return the similarity between the two objects specified by their object * ids */ - D similarity(O o1, O o2); - - /** - * Method to get the distance functions factory. - * - * @return Factory for distance objects - */ - D getDistanceFactory(); + double similarity(O o1, O o2); /** * Access the underlying data query. @@ -105,5 +95,5 @@ public interface SimilarityQuery<O, D extends Distance<?>> extends DatabaseQuery * * @return Similarity function */ - SimilarityFunction<? super O, D> getSimilarityFunction(); + SimilarityFunction<? super O> getSimilarityFunction(); }
\ No newline at end of file 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 dde6909b..720096ad 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) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |