diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/query/rknn')
5 files changed, 76 insertions, 71 deletions
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 |