diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index')
51 files changed, 1251 insertions, 226 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/AbstractRefiningIndex.java b/src/de/lmu/ifi/dbs/elki/index/AbstractRefiningIndex.java index 30abb4a4..1d42b7b3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/AbstractRefiningIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/AbstractRefiningIndex.java @@ -1,15 +1,37 @@ package de.lmu.ifi.dbs.elki.index; +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ import java.util.List; import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -24,6 +46,9 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; * * @author Erich Schubert * + * @apiviz.has AbstractRangeQuery + * @apiviz.has AbstractKNNQuery + * * @param <O> Object type */ public abstract class AbstractRefiningIndex<O> extends AbstractIndex<O> implements PageFileStatistics { @@ -112,7 +137,7 @@ public abstract class AbstractRefiningIndex<O> extends AbstractIndex<O> implemen } @Override - public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range) { + public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range) { return getRangeForObject(relation.get(id), range); } @@ -143,7 +168,7 @@ public abstract class AbstractRefiningIndex<O> extends AbstractIndex<O> implemen * * @author Erich Schubert */ - abstract public class AbstractKNNQuery<D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> implements KNNQuery<O, D> { + abstract public class AbstractKNNQuery<D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> { /** * Constructor. * @@ -164,7 +189,7 @@ public abstract class AbstractRefiningIndex<O> extends AbstractIndex<O> implemen } @Override - public KNNResult<D> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/LocalProjectionIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/LocalProjectionIndex.java index cef2fbdc..4e187a9c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/LocalProjectionIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/LocalProjectionIndex.java @@ -24,7 +24,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed; */ import de.lmu.ifi.dbs.elki.data.NumberVector; -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.index.Index; import de.lmu.ifi.dbs.elki.index.IndexFactory; @@ -44,10 +44,10 @@ public interface LocalProjectionIndex<V extends NumberVector<?, ?>, P extends Pr /** * Get the precomputed local projection for a particular object ID. * - * @param objid Object ID + * @param id Object ID * @return local projection */ - public P getLocalProjection(DBID objid); + public P getLocalProjection(DBIDRef id); /** * Factory diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/AbstractMaterializeKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/AbstractMaterializeKNNPreprocessor.java index b9b72d87..21e0abf7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/AbstractMaterializeKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/AbstractMaterializeKNNPreprocessor.java @@ -27,7 +27,7 @@ import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; -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.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; @@ -120,17 +120,17 @@ public abstract class AbstractMaterializeKNNPreprocessor<O, D extends Distance<D /** * Get the k nearest neighbors. * - * @param objid Object ID + * @param id Object ID * @return Neighbors */ - public KNNResult<D> get(DBID objid) { + public KNNResult<D> get(DBIDRef id) { if(storage == null) { if(getLogger().isDebugging()) { getLogger().debug("Running kNN preprocessor: " + this.getClass()); } preprocess(); } - return storage.get(objid); + return storage.get(id); } /** diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java index 1436efe2..c200472b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java @@ -36,6 +36,8 @@ import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs; @@ -104,9 +106,9 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends */ private void materializeKNNAndRKNNs(ArrayDBIDs ids, FiniteProgress progress) { // add an empty list to each rknn - for(DBID id : ids) { - if(materialized_RkNN.get(id) == null) { - materialized_RkNN.put(id, new TreeSet<DistanceResultPair<D>>()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + if(materialized_RkNN.get(iter) == null) { + materialized_RkNN.put(iter, new TreeSet<DistanceResultPair<D>>()); } } @@ -117,7 +119,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends KNNResult<D> kNNs = kNNList.get(i); storage.put(id, kNNs); for(DistanceResultPair<D> kNN : kNNs) { - Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(kNN.getDBID()); + Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(kNN); rknns.add(new GenericDistanceResultPair<D>(kNN.getDistance(), id)); } if(progress != null) { @@ -169,24 +171,24 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends private ArrayDBIDs updateKNNsAndRkNNs(DBIDs ids) { ArrayModifiableDBIDs rkNN_ids = DBIDUtil.newArray(); DBIDs oldids = DBIDUtil.difference(relation.getDBIDs(), ids); - for(DBID id1 : oldids) { - KNNResult<D> kNNs = storage.get(id1); + for (DBIDIter iter = oldids.iter(); iter.valid(); iter.advance()) { + KNNResult<D> kNNs = storage.get(iter); D knnDist = kNNs.getKNNDistance(); // look for new kNNs KNNHeap<D> heap = null; - for(DBID id2 : ids) { - D dist = distanceQuery.distance(id1, id2); + for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + D dist = distanceQuery.distance(iter, iter2); if(dist.compareTo(knnDist) <= 0) { if(heap == null) { heap = new KNNHeap<D>(k); heap.addAll(kNNs); } - heap.add(dist, id2); + heap.add(dist, iter2); } } if(heap != null) { KNNList<D> newKNNs = heap.toKNNList(); - storage.put(id1, newKNNs); + storage.put(iter, newKNNs); // get the difference int i = 0; @@ -196,7 +198,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends while(i < kNNs.size() && j < newKNNs.size()) { DistanceResultPair<D> drp1 = kNNs.get(i); DistanceResultPair<D> drp2 = newKNNs.get(j); - if(!drp1.equals(drp2)) { + if(!drp1.sameDBID(drp2)) { added.add(drp2); j++; } @@ -211,16 +213,16 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends } // add new RkNN for(DistanceResultPair<D> drp : added) { - Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(drp.getDBID()); - rknns.add(new GenericDistanceResultPair<D>(drp.getDistance(), id1)); + Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(drp); + rknns.add(new GenericDistanceResultPair<D>(drp.getDistance(), iter.getDBID())); } // remove old RkNN for(DistanceResultPair<D> drp : removed) { - Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(drp.getDBID()); - rknns.remove(new GenericDistanceResultPair<D>(drp.getDistance(), id1)); + Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(drp); + rknns.remove(new GenericDistanceResultPair<D>(drp.getDistance(), iter.getDBID())); } - rkNN_ids.add(id1); + rkNN_ids.add(iter); } } return rkNN_ids; @@ -237,11 +239,11 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends } List<KNNResult<D>> kNNs = new ArrayList<KNNResult<D>>(ids.size()); List<List<DistanceResultPair<D>>> rkNNs = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); - for(DBID id : aids) { - kNNs.add(storage.get(id)); - storage.delete(id); - rkNNs.add(new ArrayList<DistanceResultPair<D>>(materialized_RkNN.get(id))); - materialized_RkNN.delete(id); + for (DBIDIter iter = aids.iter(); iter.valid(); iter.advance()) { + kNNs.add(storage.get(iter)); + storage.delete(iter); + rkNNs.add(new ArrayList<DistanceResultPair<D>>(materialized_RkNN.get(iter))); + materialized_RkNN.delete(iter); } ArrayDBIDs kNN_ids = extractAndRemoveIDs(kNNs, aids); ArrayDBIDs rkNN_ids = extractAndRemoveIDs(rkNNs, aids); @@ -256,8 +258,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends DBID id = rkNN_ids.get(i); storage.put(id, kNNList.get(i)); for(DistanceResultPair<D> kNN : kNNList.get(i)) { - Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(kNN.getDBID()); - rknns.add(new GenericDistanceResultPair<D>(kNN.getDistance(), id)); + materialized_RkNN.get(kNN).add(new GenericDistanceResultPair<D>(kNN.getDistance(), id)); } } // update the RkNNs of the kNNs @@ -267,7 +268,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends SortedSet<DistanceResultPair<D>> rkNN = materialized_RkNN.get(id); for(Iterator<DistanceResultPair<D>> it = rkNN.iterator(); it.hasNext();) { DistanceResultPair<D> drp = it.next(); - if(idsSet.contains(drp.getDBID())) { + if(idsSet.contains(drp)) { it.remove(); } } @@ -300,7 +301,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends * @param id the query id * @return the RkNNs */ - public List<DistanceResultPair<D>> getRKNN(DBID id) { + public List<DistanceResultPair<D>> getRKNN(DBIDRef id) { SortedSet<DistanceResultPair<D>> rKNN = materialized_RkNN.get(id); if(rKNN == null) return null; diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java index fcd6fad1..cdc3fce4 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNPreprocessor.java @@ -31,6 +31,7 @@ import javax.swing.event.EventListenerList; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; @@ -127,9 +128,9 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra } } else { - for(DBID id : ids) { - KNNResult<D> knn = knnQuery.getKNNForDBID(id, k); - storage.put(id, knn); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + KNNResult<D> knn = knnQuery.getKNNForDBID(iter, k); + storage.put(iter, knn); if(progress != null) { progress.incrementProcessed(getLogger()); } @@ -150,8 +151,9 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra public void insertAll(DBIDs ids) { if(storage == null && ids.size() > 0) { preprocess(); + } else { + objectsInserted(ids); } - objectsInserted(ids); } @Override @@ -213,25 +215,25 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra private ArrayDBIDs updateKNNsAfterInsertion(DBIDs ids) { ArrayModifiableDBIDs rkNN_ids = DBIDUtil.newArray(); DBIDs oldids = DBIDUtil.difference(relation.getDBIDs(), ids); - for(DBID id1 : oldids) { - KNNResult<D> kNNs = storage.get(id1); + for (DBIDIter iter = oldids.iter(); iter.valid(); iter.advance()) { + KNNResult<D> kNNs = storage.get(iter); D knnDist = kNNs.get(kNNs.size() - 1).getDistance(); // look for new kNNs KNNHeap<D> heap = null; - for(DBID id2 : ids) { - D dist = distanceQuery.distance(id1, id2); + for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + D dist = distanceQuery.distance(iter, iter2); if(dist.compareTo(knnDist) <= 0) { if(heap == null) { heap = new KNNHeap<D>(k); heap.addAll(kNNs); } - heap.add(dist, id2); + heap.add(dist, iter2); } } if(heap != null) { kNNs = heap.toKNNList(); - storage.put(id1, kNNs); - rkNN_ids.add(id1); + storage.put(iter, kNNs); + rkNN_ids.add(iter); } } return rkNN_ids; @@ -247,11 +249,11 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra private ArrayDBIDs updateKNNsAfterDeletion(DBIDs ids) { SetDBIDs idsSet = DBIDUtil.ensureSet(ids); ArrayModifiableDBIDs rkNN_ids = DBIDUtil.newArray(); - for(DBID id1 : relation.iterDBIDs()) { - KNNResult<D> kNNs = storage.get(id1); + for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { + KNNResult<D> kNNs = storage.get(iditer); for(DistanceResultPair<D> kNN : kNNs) { - if(idsSet.contains(kNN.getDBID())) { - rkNN_ids.add(id1); + if(idsSet.contains(kNN)) { + rkNN_ids.add(iditer); break; } } @@ -280,8 +282,8 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra if(stepprog != null) { stepprog.beginStep(1, "New deletions ocurred, remove their materialized kNNs.", getLogger()); } - for(DBID id : ids) { - storage.delete(id); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + storage.delete(iter); } // update the affected kNNs @@ -349,11 +351,11 @@ public class MaterializeKNNPreprocessor<O, D extends Distance<D>> extends Abstra HashSetModifiableDBIDs ids = DBIDUtil.newHashSet(); for(Collection<DistanceResultPair<D>> drps : extraxt) { for(DistanceResultPair<D> drp : drps) { - ids.add(drp.getDBID()); + ids.add(drp); } } - for(DBID id : remove) { - ids.remove(id); + for (DBIDIter iter = remove.iter(); iter.valid(); iter.advance()) { + ids.remove(iter); } // Convert back to array return DBIDUtil.newArray(ids); diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MetricalIndexApproximationMaterializeKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MetricalIndexApproximationMaterializeKNNPreprocessor.java index 5ac7d2d2..d3df7855 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MetricalIndexApproximationMaterializeKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MetricalIndexApproximationMaterializeKNNPreprocessor.java @@ -28,7 +28,8 @@ import java.util.HashMap; import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -108,14 +109,14 @@ public class MetricalIndexApproximationMaterializeKNNPreprocessor<O extends Numb getLogger().debugFinest("NumEntires = " + size); } // Collect the ids in this node. - DBID[] ids = new DBID[size]; + ArrayModifiableDBIDs ids = DBIDUtil.newArray(size); for(int i = 0; i < size; i++) { - ids[i] = ((LeafEntry) node.getEntry(i)).getDBID(); + ids.add(((LeafEntry) node.getEntry(i)).getDBID()); } HashMap<DBIDPair, D> cache = new HashMap<DBIDPair, D>(size * size * 3 / 8); - for(DBID id : ids) { + for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { KNNHeap<D> kNN = new KNNHeap<D>(k, distanceQuery.infiniteDistance()); - for(DBID id2 : ids) { + for(DBIDIter id2 = ids.iter(); id2.valid(); id2.advance()) { DBIDPair key = DBIDUtil.newPair(id, id2); D d = cache.remove(key); if(d != null) { diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/PartitionApproximationMaterializeKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/PartitionApproximationMaterializeKNNPreprocessor.java index 90813b92..79c70642 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/PartitionApproximationMaterializeKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/PartitionApproximationMaterializeKNNPreprocessor.java @@ -29,7 +29,7 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -109,26 +109,26 @@ public class PartitionApproximationMaterializeKNNPreprocessor<O, D extends Dista ids.add(aids.get(i * partitions + part)); } HashMap<DBIDPair, D> cache = new HashMap<DBIDPair, D>(size * size * 3 / 8); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { KNNHeap<D> kNN = new KNNHeap<D>(k, distanceQuery.infiniteDistance()); - for(DBID id2 : ids) { - DBIDPair key = DBIDUtil.newPair(id, id2); + for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + DBIDPair key = DBIDUtil.newPair(iter, iter2); D d = cache.remove(key); if(d != null) { // consume the previous result. - kNN.add(d, id2); + kNN.add(d, iter2); } else { // compute new and store the previous result. - d = distanceQuery.distance(id, id2); - kNN.add(d, id2); + d = distanceQuery.distance(iter, iter2); + kNN.add(d, iter2); // put it into the cache, but with the keys reversed - key = DBIDUtil.newPair(id2, id); + key = DBIDUtil.newPair(iter2, iter); cache.put(key, d); } } ksize.put(kNN.size()); - storage.put(id, kNN.toKNNList()); + storage.put(iter, kNN.toKNNList()); } if(logger.isDebugging()) { if(cache.size() > 0) { diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/RandomSampleKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/RandomSampleKNNPreprocessor.java index 924c7c3c..fa868109 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/RandomSampleKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/RandomSampleKNNPreprocessor.java @@ -28,10 +28,9 @@ import java.util.Random; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -97,17 +96,17 @@ public class RandomSampleKNNPreprocessor<O, D extends Distance<D>> extends Abstr final long iseed = (seed != null) ? seed : (new Random()).nextLong(); int i = 0; - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { KNNHeap<D> kNN = new KNNHeap<D>(k, distanceQuery.infiniteDistance()); long rseed = i * 0x7FFFFFFFFFFFFFE7L + iseed; DBIDs rsamp = DBIDUtil.randomSample(ids, samplesize, rseed); - for(DBID oid : rsamp) { - D dist = distanceQuery.distance(id, oid); - kNN.add(new GenericDistanceResultPair<D>(dist, oid)); + for (DBIDIter iter2 = rsamp.iter(); iter2.valid(); iter2.advance()) { + D dist = distanceQuery.distance(iter, iter2); + kNN.add(dist, iter2); } - storage.put(id, kNN.toKNNList()); + storage.put(iter, kNN.toKNNList()); if(progress != null) { progress.incrementProcessed(getLogger()); } diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/SpatialApproximationMaterializeKNNPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/SpatialApproximationMaterializeKNNPreprocessor.java index e78f5e89..b206194b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/SpatialApproximationMaterializeKNNPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/SpatialApproximationMaterializeKNNPreprocessor.java @@ -30,7 +30,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -113,14 +114,14 @@ public class SpatialApproximationMaterializeKNNPreprocessor<O extends NumberVect getLogger().debugFinest("NumEntires = " + size); } // Collect the ids in this node. - DBID[] ids = new DBID[size]; + ArrayModifiableDBIDs ids = DBIDUtil.newArray(size); for(int i = 0; i < size; i++) { - ids[i] = ((LeafEntry) node.getEntry(i)).getDBID(); + ids.add(((LeafEntry) node.getEntry(i)).getDBID()); } HashMap<DBIDPair, D> cache = new HashMap<DBIDPair, D>(size * size * 3 / 8); - for(DBID id : ids) { + for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { KNNHeap<D> kNN = new KNNHeap<D>(k, distanceQuery.infiniteDistance()); - for(DBID id2 : ids) { + for(DBIDIter id2 = ids.iter(); id2.valid(); id2.advance()) { DBIDPair key = DBIDUtil.newPair(id, id2); D d = cache.remove(key); if(d != null) { diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/AbstractFilteredPCAIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/AbstractFilteredPCAIndex.java index 9cb2b997..99e956c8 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/AbstractFilteredPCAIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/AbstractFilteredPCAIndex.java @@ -30,6 +30,8 @@ import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -99,7 +101,8 @@ public abstract class AbstractFilteredPCAIndex<NV extends NumberVector<? extends FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("Performing local PCA", relation.size(), getLogger()) : null; // TODO: use a bulk operation? - for(DBID id : relation.iterDBIDs()) { + for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { + DBID id = iditer.getDBID(); Collection<DistanceResultPair<DoubleDistance>> objects = objectsForPCA(id); PCAFilteredResult pcares = pca.processQueryResult(objects, relation); @@ -122,7 +125,7 @@ public abstract class AbstractFilteredPCAIndex<NV extends NumberVector<? extends } @Override - public PCAFilteredResult getLocalProjection(DBID objid) { + public PCAFilteredResult getLocalProjection(DBIDRef objid) { if(storage == null) { preprocess(); } diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/FilteredLocalPCAIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/FilteredLocalPCAIndex.java index 8130f6b3..bc5d08c1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/FilteredLocalPCAIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/FilteredLocalPCAIndex.java @@ -24,7 +24,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.localpca; */ import de.lmu.ifi.dbs.elki.data.NumberVector; -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.index.preprocessed.LocalProjectionIndex; import de.lmu.ifi.dbs.elki.math.linearalgebra.pca.PCAFilteredResult; @@ -44,7 +44,7 @@ public interface FilteredLocalPCAIndex<NV extends NumberVector<?, ?>> extends Lo * @return Matrix */ @Override - public PCAFilteredResult getLocalProjection(DBID objid); + public PCAFilteredResult getLocalProjection(DBIDRef objid); /** * Factory interface diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/RangeQueryFilteredPCAIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/RangeQueryFilteredPCAIndex.java index 7d5da770..99937dbf 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/RangeQueryFilteredPCAIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/localpca/RangeQueryFilteredPCAIndex.java @@ -23,12 +23,10 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.localpca; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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.DBID; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -86,7 +84,7 @@ public class RangeQueryFilteredPCAIndex<NV extends NumberVector<? extends NV, ?> } @Override - protected List<DistanceResultPair<DoubleDistance>> objectsForPCA(DBID id) { + protected DistanceDBIDResult<DoubleDistance> objectsForPCA(DBID id) { return rangeQuery.getRangeForDBID(id, epsilon); } diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/AbstractPreferenceVectorIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/AbstractPreferenceVectorIndex.java index 95c698ee..387985ab 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/AbstractPreferenceVectorIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/AbstractPreferenceVectorIndex.java @@ -28,7 +28,7 @@ import java.util.BitSet; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.data.type.TypeUtil; -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.index.preprocessed.AbstractPreprocessorIndex; import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable; @@ -56,7 +56,7 @@ public abstract class AbstractPreferenceVectorIndex<NV extends NumberVector<?, ? abstract protected void preprocess(); @Override - public BitSet getPreferenceVector(DBID objid) { + public BitSet getPreferenceVector(DBIDRef objid) { if(storage == null) { preprocess(); } diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/DiSHPreferenceVectorIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/DiSHPreferenceVectorIndex.java index ade6c114..416a5ffb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/DiSHPreferenceVectorIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/DiSHPreferenceVectorIndex.java @@ -27,7 +27,6 @@ import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; import java.util.HashMap; -import java.util.Iterator; import java.util.List; import java.util.Map; @@ -42,9 +41,11 @@ import de.lmu.ifi.dbs.elki.database.UpdatableDatabase; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; @@ -161,9 +162,9 @@ public class DiSHPreferenceVectorIndex<V extends NumberVector<?, ?>> extends Abs // epsilons as string RangeQuery<V, DoubleDistance>[] rangeQueries = initRangeQueries(relation, dim); - for(Iterator<DBID> it = relation.iterDBIDs(); it.hasNext();) { + for(DBIDIter it = relation.iterDBIDs(); it.valid(); it.advance()) { StringBuffer msg = new StringBuffer(); - final DBID id = it.next(); + final DBID id = it.getDBID(); if(logger.isDebugging()) { msg.append("\nid = ").append(id); @@ -174,7 +175,7 @@ public class DiSHPreferenceVectorIndex<V extends NumberVector<?, ?>> extends Abs // determine neighbors in each dimension ModifiableDBIDs[] allNeighbors = ClassGenericsUtil.newArrayOfNull(dim, ModifiableDBIDs.class); for(int d = 0; d < dim; d++) { - List<DistanceResultPair<DoubleDistance>> qrList = rangeQueries[d].getRangeForDBID(id, epsilon[d]); + DistanceDBIDResult<DoubleDistance> qrList = rangeQueries[d].getRangeForDBID(id, epsilon[d]); allNeighbors[d] = DBIDUtil.newHashSet(qrList.size()); for(DistanceResultPair<DoubleDistance> qr : qrList) { allNeighbors[d].add(qr.getDBID()); @@ -260,8 +261,8 @@ public class DiSHPreferenceVectorIndex<V extends NumberVector<?, ?>> extends Abs // database for apriori UpdatableDatabase apriori_db = new HashmapDatabase(); SimpleTypeInformation<?> bitmeta = VectorFieldTypeInformation.get(BitVector.class, dimensionality); - for(Iterator<DBID> it = relation.iterDBIDs(); it.hasNext();) { - DBID id = it.next(); + for(DBIDIter it = relation.iterDBIDs(); it.valid(); it.advance()) { + DBID id = it.getDBID(); Bit[] bits = new Bit[dimensionality]; boolean allFalse = true; for(int d = 0; d < dimensionality; d++) { diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/HiSCPreferenceVectorIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/HiSCPreferenceVectorIndex.java index 44ddb17c..65f5f61e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/HiSCPreferenceVectorIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/HiSCPreferenceVectorIndex.java @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.preference; */ import java.util.BitSet; -import java.util.Iterator; import de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.HiSC; import de.lmu.ifi.dbs.elki.data.NumberVector; @@ -32,6 +31,7 @@ import de.lmu.ifi.dbs.elki.database.QueryUtil; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; @@ -107,9 +107,8 @@ public class HiSCPreferenceVectorIndex<V extends NumberVector<?, ?>> extends Abs KNNQuery<V, DoubleDistance> knnQuery = QueryUtil.getKNNQuery(relation, EuclideanDistanceFunction.STATIC, k); - Iterator<DBID> it = relation.iterDBIDs(); - while(it.hasNext()) { - DBID id = it.next(); + for (DBIDIter it = relation.iterDBIDs(); it.valid(); it.advance()) { + DBID id = it.getDBID(); if(logger.isDebugging()) { msg.append("\n\nid = ").append(id); diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/PreferenceVectorIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/PreferenceVectorIndex.java index c01e9ddb..a0fba8f3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/PreferenceVectorIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/preference/PreferenceVectorIndex.java @@ -26,7 +26,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.preference; import java.util.BitSet; import de.lmu.ifi.dbs.elki.data.NumberVector; -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.index.Index; import de.lmu.ifi.dbs.elki.index.IndexFactory; @@ -42,10 +42,10 @@ public interface PreferenceVectorIndex<NV extends NumberVector<?, ?>> extends In /** * Get the precomputed preference vector for a particular object ID. * - * @param objid Object ID + * @param id Object ID * @return Matrix */ - public BitSet getPreferenceVector(DBID objid); + public BitSet getPreferenceVector(DBIDRef id); /** * Factory interface diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborIndex.java index 7efe26e0..3aa0c523 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborIndex.java @@ -24,7 +24,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.snn; */ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.index.Index; import de.lmu.ifi.dbs.elki.index.IndexFactory; @@ -38,10 +38,10 @@ public interface SharedNearestNeighborIndex<O> extends Index { /** * Get the precomputed nearest neighbors * - * @param objid Object ID + * @param id Object ID * @return Neighbor DBIDs */ - public ArrayDBIDs getNearestNeighborSet(DBID objid); + public ArrayDBIDs getNearestNeighborSet(DBIDRef id); /** * Get the number of neighbors diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborPreprocessor.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborPreprocessor.java index 46f47a33..e4d96028 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborPreprocessor.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/snn/SharedNearestNeighborPreprocessor.java @@ -29,8 +29,10 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -112,13 +114,12 @@ public class SharedNearestNeighborPreprocessor<O, D extends Distance<D>> extends KNNQuery<O, D> knnquery = QueryUtil.getKNNQuery(relation, distanceFunction, numberOfNeighbors); FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("assigning nearest neighbor lists", relation.size(), getLogger()) : null; - for(DBID id : relation.iterDBIDs()) { + for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { ArrayModifiableDBIDs neighbors = DBIDUtil.newArray(numberOfNeighbors); - KNNResult<D> kNN = knnquery.getKNNForDBID(id, numberOfNeighbors); - for(int i = 0; i < kNN.size(); i++) { - final DBID nid = kNN.get(i).getDBID(); + KNNResult<D> kNN = knnquery.getKNNForDBID(iditer, numberOfNeighbors); + for(DistanceResultPair<D> pair : kNN) { // if(!id.equals(nid)) { - neighbors.add(nid); + neighbors.add(pair); // } // Size limitation to exactly numberOfNeighbors if(neighbors.size() >= numberOfNeighbors) { @@ -126,7 +127,7 @@ public class SharedNearestNeighborPreprocessor<O, D extends Distance<D>> extends } } neighbors.sort(); - storage.put(id, neighbors); + storage.put(iditer, neighbors); if(progress != null) { progress.incrementProcessed(getLogger()); } @@ -137,7 +138,7 @@ public class SharedNearestNeighborPreprocessor<O, D extends Distance<D>> extends } @Override - public ArrayDBIDs getNearestNeighborSet(DBID objid) { + public ArrayDBIDs getNearestNeighborSet(DBIDRef objid) { if(storage == null) { preprocess(); } diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/AbstractSubspaceProjectionIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/AbstractSubspaceProjectionIndex.java index 4a265fc9..da16dd08 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/AbstractSubspaceProjectionIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/AbstractSubspaceProjectionIndex.java @@ -23,9 +23,6 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.subspaceproj; 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.algorithm.clustering.AbstractProjectedDBSCAN; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; @@ -33,8 +30,11 @@ import de.lmu.ifi.dbs.elki.data.type.TypeUtil; import de.lmu.ifi.dbs.elki.database.QueryUtil; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -114,20 +114,20 @@ public abstract class AbstractSubspaceProjectionIndex<NV extends NumberVector<?, RangeQuery<NV, D> rangeQuery = QueryUtil.getRangeQuery(relation, rangeQueryDistanceFunction); FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress(this.getClass().getName(), relation.size(), getLogger()) : null; - for(DBID id : relation.iterDBIDs()) { - List<DistanceResultPair<D>> neighbors = rangeQuery.getRangeForDBID(id, epsilon); + for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { + DistanceDBIDResult<D> neighbors = rangeQuery.getRangeForDBID(iditer, epsilon); final P pres; if(neighbors.size() >= minpts) { - pres = computeProjection(id, neighbors, relation); + pres = computeProjection(iditer, neighbors, relation); } else { - DistanceResultPair<D> firstQR = neighbors.get(0); - neighbors = new ArrayList<DistanceResultPair<D>>(); + DistanceResultPair<D> firstQR = neighbors.iterator().next(); + neighbors = new GenericDistanceDBIDList<D>(); neighbors.add(firstQR); - pres = computeProjection(id, neighbors, relation); + pres = computeProjection(iditer, neighbors, relation); } - storage.put(id, pres); + storage.put(iditer, pres); if(progress != null) { progress.incrementProcessed(getLogger()); @@ -146,7 +146,7 @@ public abstract class AbstractSubspaceProjectionIndex<NV extends NumberVector<?, } @Override - public P getLocalProjection(DBID objid) { + public P getLocalProjection(DBIDRef objid) { if(storage == null) { preprocess(); } @@ -167,7 +167,7 @@ public abstract class AbstractSubspaceProjectionIndex<NV extends NumberVector<?, * * @return local subspace projection */ - protected abstract P computeProjection(DBID id, List<DistanceResultPair<D>> neighbors, Relation<NV> relation); + protected abstract P computeProjection(DBIDRef id, DistanceDBIDResult<D> neighbors, Relation<NV> relation); /** * Factory class diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/FourCSubspaceIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/FourCSubspaceIndex.java index 83a9469c..e61b9144 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/FourCSubspaceIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/FourCSubspaceIndex.java @@ -24,12 +24,12 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.subspaceproj; */ import java.util.ArrayList; -import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; -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.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -93,7 +93,7 @@ public class FourCSubspaceIndex<V extends NumberVector<V, ?>, D extends Distance } @Override - protected PCAFilteredResult computeProjection(DBID id, List<DistanceResultPair<D>> neighbors, Relation<V> database) { + protected PCAFilteredResult computeProjection(DBIDRef id, DistanceDBIDResult<D> neighbors, Relation<V> database) { ModifiableDBIDs ids = DBIDUtil.newArray(neighbors.size()); for(DistanceResultPair<D> neighbor : neighbors) { ids.add(neighbor.getDBID()); diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/PreDeConSubspaceIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/PreDeConSubspaceIndex.java index 1e83ae80..34bfb5e9 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/PreDeConSubspaceIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/PreDeConSubspaceIndex.java @@ -23,10 +23,9 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.subspaceproj; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - import de.lmu.ifi.dbs.elki.data.NumberVector; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -87,7 +86,7 @@ public class PreDeConSubspaceIndex<V extends NumberVector<? extends V, ?>, D ext } @Override - protected SubspaceProjectionResult computeProjection(DBID id, List<DistanceResultPair<D>> neighbors, Relation<V> database) { + protected SubspaceProjectionResult computeProjection(DBIDRef id, DistanceDBIDResult<D> neighbors, Relation<V> database) { StringBuffer msg = null; int referenceSetSize = neighbors.size(); diff --git a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/SubspaceProjectionIndex.java b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/SubspaceProjectionIndex.java index d5070986..210db8f6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/SubspaceProjectionIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/preprocessed/subspaceproj/SubspaceProjectionIndex.java @@ -24,7 +24,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.subspaceproj; */ import de.lmu.ifi.dbs.elki.data.NumberVector; -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.index.preprocessed.LocalProjectionIndex; import de.lmu.ifi.dbs.elki.math.linearalgebra.ProjectionResult; @@ -46,7 +46,7 @@ public interface SubspaceProjectionIndex<NV extends NumberVector<?, ?>, P extend * @return Matrix */ @Override - public P getLocalProjection(DBID objid); + public P getLocalProjection(DBIDRef objid); /** * Factory interface diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java index 5e949e0b..a35a4057 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java @@ -29,6 +29,7 @@ import java.util.List; import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; @@ -378,7 +379,8 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { E p = node.getEntry(i); - for(DBID q : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID q = iter.getDBID(); KNNHeap<D> knns_q = knnLists.get(q); D knn_q_maxDist = knns_q.getKNNDistance(); @@ -393,7 +395,8 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract List<DistanceEntry<D, E>> entries = getSortedEntries(node, ids); for(DistanceEntry<D, E> distEntry : entries) { D minDist = distEntry.getDistance(); - for(DBID q : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID q = iter.getDBID(); KNNHeap<D> knns_q = knnLists.get(q); D knn_q_maxDist = knns_q.getKNNDistance(); @@ -446,8 +449,8 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract E entry = node.getEntry(i); D minMinDist = getDistanceFactory().infiniteDistance(); - for(DBID q : ids) { - D distance = distanceQuery.distance(entry.getRoutingObjectID(), q); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + D distance = distanceQuery.distance(entry.getRoutingObjectID(), iter.getDBID()); D minDist = entry.getCoveringRadius().compareTo(distance) > 0 ? getDistanceFactory().nullDistance() : distance.minus(entry.getCoveringRadius()); minMinDist = DistanceUtil.max(minMinDist, minDist); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java index ffd38a74..9391a2fa 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java @@ -25,7 +25,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; @@ -66,5 +66,5 @@ public abstract class AbstractMkTree<O, D extends Distance<D>, N extends Abstrac * @param k the number of nearest neighbors to be returned * @return a List of the query results */ - public abstract List<DistanceResultPair<D>> reverseKNNQuery(final DBID id, int k); + public abstract List<DistanceResultPair<D>> reverseKNNQuery(final DBIDRef id, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java index 5f92ba70..0f15a4a9 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java @@ -32,6 +32,8 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; @@ -176,7 +178,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a List of the query results */ @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBID id, int k) { + public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { List<DistanceResultPair<D>> result = doReverseKNNQuery(k, id); Collections.sort(result); return result; @@ -243,7 +245,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param q the id of the query object * @return the result of the reverse knn query */ - private List<DistanceResultPair<D>> doReverseKNNQuery(int k, DBID q) { + private List<DistanceResultPair<D>> doReverseKNNQuery(int k, DBIDRef q) { List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); @@ -296,7 +298,8 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree private List<D> getMeanKNNList(DBIDs ids, Map<DBID, KNNList<D>> knnLists) { double[] means = new double[k_max]; - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); KNNList<D> knns = knnLists.get(id); List<D> knnDists = knns.asDistanceList(); for(int k = 0; k < k_max; k++) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java index eedc52ed..90c31676 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java @@ -27,6 +27,7 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -99,7 +100,8 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree @Override public void insertAll(DBIDs ids) { List<MkAppEntry<D>> objs = new ArrayList<MkAppEntry<D>>(ids.size()); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java index 83e60e0e..2ad3558e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java @@ -34,7 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.FormatUtil; * Provides an polynomial approximation bo + b1*k + b2*k^2 + ... + bp*k^p * for knn-distances consisting of parameters b0, ..., bp. * - * @author Elke Achtert + * @author Elke Achtert */ public class PolynomialApproximation implements Externalizable { private static final long serialVersionUID = 1; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java index 7fe67a03..26ae17db 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java @@ -31,6 +31,8 @@ import java.util.Map; import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; @@ -171,7 +173,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a List of the query results */ @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBID id, int k) { + public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { if(k > this.k_max) { throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MCop-Tree!"); } @@ -182,8 +184,8 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // refinement of candidates Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(); - for(DBID cid : candidates) { - knnLists.put(cid, new KNNHeap<D>(k, getDistanceQuery().infiniteDistance())); + for (DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { + knnLists.put(iter.getDBID(), new KNNHeap<D>(k, getDistanceQuery().infiniteDistance())); } batchNN(getRoot(), candidates, knnLists); @@ -193,7 +195,8 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree rkNNStatistics.addCandidates(candidates.size()); rkNNStatistics.addTrueHits(result.size()); - for(DBID cid : candidates) { + for (DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { + DBID cid = iter.getDBID(); for(DistanceResultPair<D> qr : knnLists.get(id)) { if(qr.getDBID().equals(id)) { result.add(new GenericDistanceResultPair<D>(qr.getDistance(), cid)); @@ -285,7 +288,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param candidates holds possible candidates for the result (they need a * refinement) */ - private void doReverseKNNQuery(int k, DBID q, List<DistanceResultPair<D>> result, ModifiableDBIDs candidates) { + private void doReverseKNNQuery(int k, DBIDRef q, List<DistanceResultPair<D>> result, ModifiableDBIDs candidates) { final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); // push root diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java index 2c4ffb06..460e15b7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java @@ -27,6 +27,7 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -98,7 +99,8 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree @Override public void insertAll(DBIDs ids) { List<MkCoPEntry<D>> objs = new ArrayList<MkCoPEntry<D>>(ids.size()); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java index 5b7dc8fc..f9f77723 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java @@ -30,6 +30,8 @@ import java.util.List; import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; @@ -88,7 +90,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * in a second step. */ @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBID id, int k) { + public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { if(k > this.getKmax()) { throw new IllegalArgumentException("Parameter k has to be equal or less than " + "parameter k of the MkMax-Tree!"); } @@ -115,7 +117,8 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O batchNN(getRoot(), candidateIDs, knnLists); List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); - for(DBID cid : candidateIDs) { + for (DBIDIter iter = candidateIDs.iter(); iter.valid(); iter.advance()) { + DBID cid = iter.getDBID(); for(DistanceResultPair<D> qr : knnLists.get(cid)) { if(id.equals(qr.getDBID())) { result.add(new GenericDistanceResultPair<D>(qr.getDistance(), cid)); @@ -191,7 +194,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * @param node_entry the entry representing the node * @param result the list for the query result */ - private void doReverseKNNQuery(DBID q, MkMaxTreeNode<O, D> node, MkMaxEntry<D> node_entry, List<DistanceResultPair<D>> result) { + private void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O, D> node, MkMaxEntry<D> node_entry, List<DistanceResultPair<D>> result) { // data node if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java index 9e1b6d6b..d1fd2b0f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java @@ -27,6 +27,7 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -84,7 +85,8 @@ public class MkMaxTreeIndex<O, D extends Distance<D>> extends MkMaxTree<O, D> im @Override public void insertAll(DBIDs ids) { List<MkMaxEntry<D>> objs = new ArrayList<MkMaxEntry<D>>(ids.size()); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java index 88000f5d..ba938fd3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java @@ -33,7 +33,7 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; * Additionally to an entry in an M-Tree an MkTabEntry holds a list of knn distances * for for parameters k <= k_max of the underlying data object or MkTab-Tree node. * - * @author Elke Achtert + * @author Elke Achtert */ interface MkTabEntry<D extends Distance<D>> extends MTreeEntry<D> { /** diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java index 750dfb72..433a01fa 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java @@ -29,6 +29,7 @@ import java.util.List; import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -90,7 +91,7 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O } @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBID id, int k) { + public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { if(k > this.getKmax()) { throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MkTab-Tree!"); } @@ -209,7 +210,7 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * @param node the root of the subtree * @param result the list holding the query result */ - private void doReverseKNNQuery(int k, DBID q, MkTabEntry<D> node_entry, MkTabTreeNode<O, D> node, List<DistanceResultPair<D>> result) { + private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry<D> node_entry, MkTabTreeNode<O, D> node, List<DistanceResultPair<D>> result) { // data node if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java index 0eb54bd1..f1d23bfd 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java @@ -27,6 +27,7 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -115,7 +116,8 @@ public class MkTabTreeIndex<O, D extends Distance<D>> extends MkTabTree<O, D> im @Override public void insertAll(DBIDs ids) { List<MkTabEntry<D>> objs = new ArrayList<MkTabEntry<D>>(ids.size()); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java index 9bcd1b02..fe60c04d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java @@ -27,6 +27,7 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -88,7 +89,8 @@ public class MTreeIndex<O, D extends Distance<D>> extends MTree<O, D> implements @Override public void insertAll(DBIDs ids) { List<MTreeEntry<D>> objs = new ArrayList<MTreeEntry<D>>(ids.size()); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java index b591f700..c2450988 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java @@ -28,6 +28,7 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; @@ -155,7 +156,7 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis } @Override - public KNNResult<D> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java index 8536cc52..e2df2dc7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java @@ -23,12 +23,14 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.Collections; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; @@ -177,8 +179,8 @@ public class MetricalIndexRangeQuery<O, D extends Distance<D>> extends AbstractD } @Override - public List<DistanceResultPair<D>> getRangeForObject(O obj, D range) { - final List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); + public DistanceDBIDResult<D> getRangeForObject(O obj, D range) { + final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); doRangeQuery(null, index.getRoot(), obj, range, result); @@ -188,7 +190,7 @@ public class MetricalIndexRangeQuery<O, D extends Distance<D>> extends AbstractD } @Override - public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range) { + public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range) { return getRangeForObject(relation.get(id), range); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java index 370f26ad..067c3abe 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java @@ -26,7 +26,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.AbstractRKNNQuery; @@ -65,7 +65,7 @@ public class MkTreeRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQuery } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k) { + public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { return index.reverseKNNQuery(id, k); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java index e50e0cb4..3bac751c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java @@ -35,7 +35,7 @@ import de.lmu.ifi.dbs.elki.data.HyperBoundingBox; import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.data.spatial.SpatialUtil; -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.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.index.tree.BreadthFirstEnumeration; import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; @@ -68,10 +68,10 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @apiviz.landmark * @apiviz.has AbstractRStarTreeNode oneway - - contains - * @apiviz.uses Enlargement * @apiviz.composedOf BulkSplit * @apiviz.composedOf SplitStrategy * @apiviz.composedOf InsertionStrategy + * @apiviz.composedOf OverflowTreatment * * @param <N> Node type * @param <E> Entry type @@ -196,11 +196,11 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @return the path to the leaf entry of the specified subtree that represents * the data object with the specified mbr and id */ - protected IndexTreePath<E> findPathToObject(IndexTreePath<E> subtree, SpatialComparable mbr, DBID id) { + protected IndexTreePath<E> findPathToObject(IndexTreePath<E> subtree, SpatialComparable mbr, DBIDRef id) { N node = getNode(subtree.getLastPathComponent().getEntry()); if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { - if(((LeafEntry) node.getEntry(i)).getDBID().equals(id)) { + if(((LeafEntry) node.getEntry(i)).getDBID().sameDBID(id)) { return subtree.pathByAddingChild(new TreeIndexPathComponent<E>(node.getEntry(i), i)); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java index 19cf8a32..8b279268 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java @@ -30,7 +30,7 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; * Additionally to an entry in an R*-Tree two boolean flags that indicate whether this entry's node * contains handled or unhandled data objects. * - * @author Elke Achtert + * @author Elke Achtert */ public interface DeLiCluEntry extends SpatialEntry { /** diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java index c7cfc493..9848f121 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java @@ -32,7 +32,7 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; * Additionally to a leaf entry in an R*-Tree two boolean flags that indicate whether this entry's node * contains handled or unhandled data objects. * - * @author Elke Achtert + * @author Elke Achtert */ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEntry { private static final long serialVersionUID = 1; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java index dd523ef8..dd3b4d6b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java @@ -28,6 +28,7 @@ import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; @@ -150,14 +151,14 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree // Make an example leaf if(canBulkLoad()) { List<DeLiCluEntry> leafs = new ArrayList<DeLiCluEntry>(ids.size()); - for(DBID id : ids) { - leafs.add(createNewLeafEntry(id)); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + leafs.add(createNewLeafEntry(iter.getDBID())); } bulkLoad(leafs); } else { - for(DBID id : ids) { - insert(id); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + insert(iter.getDBID()); } } @@ -184,8 +185,8 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override public void deleteAll(DBIDs ids) { - for(DBID id : ids) { - delete(id); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + delete(iter.getDBID()); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java index 9174dc94..f0acc233 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java @@ -33,6 +33,8 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; @@ -214,8 +216,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); double minMinDist = Double.MAX_VALUE; - for(DBID id : ids) { - double minDist = distanceFunction.doubleMinDist(entry, relation.get(id)); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + double minDist = distanceFunction.doubleMinDist(entry, relation.get(iter)); tree.distanceCalcs++; minMinDist = Math.min(minDist, minMinDist); } @@ -273,7 +275,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } @Override - public KNNResult<DoubleDistance> getKNNForDBID(DBID id, int k) { + public KNNResult<DoubleDistance> getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @@ -285,14 +287,16 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend // While this works, it seems to be slow at least for large sets! final Map<DBID, KNNHeap<DoubleDistance>> knnLists = new HashMap<DBID, KNNHeap<DoubleDistance>>(ids.size()); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); knnLists.put(id, new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance())); } batchNN(tree.getRoot(), knnLists); List<KNNResult<DoubleDistance>> result = new ArrayList<KNNResult<DoubleDistance>>(); - for(DBID id : ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = iter.getDBID(); result.add(knnLists.get(id).toKNNList()); } return result; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java index 069db6d4..1a861c3e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java @@ -23,14 +23,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.Collections; -import java.util.List; 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.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; @@ -91,8 +90,8 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte * @param epsilon Query range * @return Objects contained in query range. */ - protected List<DistanceResultPair<DoubleDistance>> doRangeQuery(O object, double epsilon) { - final List<DistanceResultPair<DoubleDistance>> result = new ArrayList<DistanceResultPair<DoubleDistance>>(); + protected GenericDistanceDBIDList<DoubleDistance> doRangeQuery(O object, double epsilon) { + final GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(); // push root @@ -130,12 +129,12 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte } @Override - public List<DistanceResultPair<DoubleDistance>> getRangeForObject(O obj, DoubleDistance range) { + public DistanceDBIDResult<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { return doRangeQuery(obj, range.doubleValue()); } @Override - public List<DistanceResultPair<DoubleDistance>> getRangeForDBID(DBID id, DoubleDistance range) { + public DistanceDBIDResult<DoubleDistance> getRangeForDBID(DBIDRef id, DoubleDistance range) { return getRangeForObject(relation.get(id), range); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java index 5129f5ca..09ebb61a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java @@ -33,6 +33,8 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; @@ -219,8 +221,8 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); D minMinDist = distanceQuery.getDistanceFactory().infiniteDistance(); - for(DBID id : ids) { - D minDist = distanceFunction.minDist(entry, relation.get(id)); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + D minDist = distanceFunction.minDist(entry, relation.get(iter)); minMinDist = DistanceUtil.min(minDist, minMinDist); } result.add(new DistanceEntry<D, SpatialEntry>(entry, minMinDist, i)); @@ -242,7 +244,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } @Override - public KNNResult<D> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @@ -253,15 +255,15 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } // While this works, it seems to be slow at least for large sets! final Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(ids.size()); - for(DBID id : ids) { - knnLists.put(id, new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + knnLists.put(iter.getDBID(), new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance())); } batchNN(tree.getRoot(), knnLists); List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(); - for(DBID id : ids) { - result.add(knnLists.get(id).toKNNList()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + result.add(knnLists.get(iter.getDBID()).toKNNList()); } return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java index d2086cb1..3b312ed7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java @@ -23,13 +23,12 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.Collections; -import java.util.List; 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.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; @@ -90,8 +89,8 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D * @param epsilon Query range * @return Objects contained in query range. */ - protected List<DistanceResultPair<D>> doRangeQuery(O object, D epsilon) { - final List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); + protected GenericDistanceDBIDList<D> doRangeQuery(O object, D epsilon) { + final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(); // push root @@ -128,12 +127,12 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D } @Override - public List<DistanceResultPair<D>> getRangeForObject(O obj, D range) { + public DistanceDBIDResult<D> getRangeForObject(O obj, D range) { return doRangeQuery(obj, range); } @Override - public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range) { + public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range) { return getRangeForObject(relation.get(id), range); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java index 46ef2628..ab136926 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java @@ -28,6 +28,7 @@ import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; @@ -109,14 +110,14 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl // Make an example leaf if(canBulkLoad()) { List<SpatialEntry> leafs = new ArrayList<SpatialEntry>(ids.size()); - for(DBID id : ids) { - leafs.add(createNewLeafEntry(id)); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + leafs.add(createNewLeafEntry(iter.getDBID())); } bulkLoad(leafs); } else { - for(DBID id : ids) { - insert(id); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + insert(iter.getDBID()); } } @@ -143,8 +144,8 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl @Override public void deleteAll(DBIDs ids) { - for(DBID id : ids) { - delete(id); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + delete(iter.getDBID()); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java index 418e92c5..a1dfbdb0 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java @@ -50,7 +50,7 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; * * @author Erich Schubert * @author Franz Graf - * @author Marisa Petri + * @author Marisa Thoma */ @Reference(authors = "N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger", title = "The R*-tree: an efficient and robust access method for points and rectangles", booktitle = "Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990", url = "http://dx.doi.org/10.1145/93597.98741") public class ApproximativeLeastOverlapInsertionStrategy extends LeastOverlapInsertionStrategy { diff --git a/src/de/lmu/ifi/dbs/elki/index/vafile/DAFile.java b/src/de/lmu/ifi/dbs/elki/index/vafile/DAFile.java new file mode 100644 index 00000000..f99f5918 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/vafile/DAFile.java @@ -0,0 +1,111 @@ +package de.lmu.ifi.dbs.elki.index.vafile;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures +
+ Copyright (C) 2011
+ 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.Arrays;
+
+import de.lmu.ifi.dbs.elki.data.NumberVector;
+import de.lmu.ifi.dbs.elki.database.ids.DBID;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
+import de.lmu.ifi.dbs.elki.database.relation.Relation;
+import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
+
+/**
+ * Dimension approximation file, a one-dimensional part of the
+ * {@link PartialVAFile}.
+ *
+ * Reference:
+ * <p>
+ * Hans-Peter Kriegel, Peer Kröger, Matthias Schubert, Ziyue Zhu:<br />
+ * Efficient Query Processing in Arbitrary Subspaces Using Vector Approximations
+ * <br />
+ * in Proc. 18th Int. Conf. on Scientific and Statistical Database Management
+ * (SSDBM 06), Wien, Austria, 2006.
+ * </p>
+ *
+ * @author Thomas Bernecker
+ * @author Erich Schubert
+ */
+@Reference(authors = "Hans-Peter Kriegel, Peer Kröger, Matthias Schubert, Ziyue Zhu", title = "Efficient Query Processing in Arbitrary Subspaces Using Vector Approximations", booktitle = "Proc. 18th Int. Conf. on Scientific and Statistical Database Management (SSDBM 06), Wien, Austria, 2006", url = "http://dx.doi.org/10.1109/SSDBM.2006.23")
+public class DAFile {
+ /**
+ * Dimension of this approximation file
+ */
+ final private int dimension;
+
+ /**
+ * Splitting grid
+ */
+ final private double[] splitPositions;
+
+ /**
+ * Constructor.
+ *
+ * @param dimension Dimension of this file
+ */
+ public DAFile(Relation<? extends NumberVector<?, ?>> relation, int dimension, int partitions) {
+ final int size = relation.size();
+ this.dimension = dimension;
+ this.splitPositions = new double[partitions + 1];
+
+ double[] tempdata = new double[size];
+ int j = 0;
+ for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { + DBID id = iditer.getDBID();
+ tempdata[j] = relation.get(id).doubleValue(dimension + 1);
+ j += 1;
+ }
+ Arrays.sort(tempdata);
+
+ for(int b = 0; b < partitions; b++) {
+ int start = (int) (b * size / (double) partitions);
+ splitPositions[b] = tempdata[start];
+ }
+ // make sure that last object will be included
+ splitPositions[partitions] = tempdata[size - 1] + 0.000001;
+ }
+
+ /**
+ * @return the split positions
+ */
+ public double[] getSplitPositions() {
+ return splitPositions;
+ }
+
+ /**
+ * @return the dimension
+ */
+ public int getDimension() {
+ return dimension;
+ }
+
+ /**
+ * Estimate the IO costs for this index.
+ *
+ * @return IO costs
+ */
+ public int getIOCosts() {
+ return splitPositions.length * 8 + 4;
+ }
+}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/vafile/PartialVAFile.java b/src/de/lmu/ifi/dbs/elki/index/vafile/PartialVAFile.java new file mode 100644 index 00000000..848597d6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/vafile/PartialVAFile.java @@ -0,0 +1,838 @@ +package de.lmu.ifi.dbs.elki.index.vafile;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures +
+ Copyright (C) 2011
+ 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.Arrays;
+import java.util.BitSet;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.lmu.ifi.dbs.elki.data.NumberVector;
+import de.lmu.ifi.dbs.elki.data.type.TypeInformation;
+import de.lmu.ifi.dbs.elki.data.type.TypeUtil;
+import de.lmu.ifi.dbs.elki.database.ids.DBID;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
+import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery;
+import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult;
+import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair;
+import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList;
+import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery;
+import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
+import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult;
+import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery;
+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.distancefunction.LPNormDistanceFunction;
+import de.lmu.ifi.dbs.elki.distance.distancefunction.subspace.SubspaceLPNormDistanceFunction;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
+import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
+import de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex;
+import de.lmu.ifi.dbs.elki.index.IndexFactory;
+import de.lmu.ifi.dbs.elki.index.KNNIndex;
+import de.lmu.ifi.dbs.elki.index.RangeIndex;
+import de.lmu.ifi.dbs.elki.index.tree.TreeIndexFactory;
+import de.lmu.ifi.dbs.elki.logging.Logging;
+import de.lmu.ifi.dbs.elki.math.MathUtil;
+import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector;
+import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNList;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.TopBoundedHeap;
+import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter;
+import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair;
+
+/**
+ * PartialVAFile. In-memory only implementation.
+ *
+ * Reference:
+ * <p>
+ * Hans-Peter Kriegel, Peer Kröger, Matthias Schubert, Ziyue Zhu:<br />
+ * Efficient Query Processing in Arbitrary Subspaces Using Vector Approximations
+ * <br />
+ * in Proc. 18th Int. Conf. on Scientific and Statistical Database Management
+ * (SSDBM 06), Wien, Austria, 2006.
+ * </p>
+ *
+ * @author Thomas Bernecker
+ * @author Erich Schubert
+ *
+ * @apiviz.landmark
+ *
+ * @apiviz.composedOf DAFile
+ * @apiviz.uses PartialVACandidate
+ * @apiviz.has PartialVAFileRangeQuery
+ * @apiviz.has PartialVAFileKNNQuery
+ */
+@Reference(authors = "Hans-Peter Kriegel, Peer Kröger, Matthias Schubert, Ziyue Zhu", title = "Efficient Query Processing in Arbitrary Subspaces Using Vector Approximations", booktitle = "Proc. 18th Int. Conf. on Scientific and Statistical Database Management (SSDBM 06), Wien, Austria, 2006", url = "http://dx.doi.org/10.1109/SSDBM.2006.23")
+public class PartialVAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex<V> implements KNNIndex<V>, RangeIndex<V> {
+ /**
+ * Class logger
+ */
+ private static final Logging logger = Logging.getLogger(PartialVAFile.class);
+
+ /**
+ * Partial VA files
+ */
+ List<DAFile> daFiles;
+
+ /**
+ * Number of partitions
+ */
+ private final int partitions;
+
+ /**
+ * Page size
+ */
+ private final int pageSize;
+
+ /**
+ * Splitting grid
+ */
+ private double[][] splitPartitions;
+
+ /**
+ * Statistics
+ */
+ protected Statistics stats;
+
+ /**
+ * The (full - we are in-memory only right now) vector approximations.
+ */
+ private ArrayList<VectorApproximation> vectorApprox;
+
+ /**
+ * Constructor.
+ *
+ * @param pageSize Page size
+ * @param relation Data relation
+ * @param partitions Number of partitions
+ */
+ public PartialVAFile(int pageSize, Relation<V> relation, int partitions) {
+ super(relation);
+ this.pageSize = pageSize;
+ this.partitions = partitions;
+ this.stats = new Statistics();
+ }
+
+ @Override
+ public void initialize(Relation<V> relation, DBIDs ids) throws IllegalStateException {
+ if(splitPartitions != null) {
+ throw new IllegalStateException("Data already inserted.");
+ }
+
+ if((Math.log(partitions) / MathUtil.LOG2) != (int) (Math.log(partitions) / MathUtil.LOG2)) {
+ throw new IllegalArgumentException("Number of partitions must be a power of 2!");
+ }
+
+ final int dimensions = DatabaseUtil.dimensionality(relation);
+
+ splitPartitions = new double[dimensions][];
+ daFiles = new ArrayList<DAFile>(dimensions);
+ for(int d = 0; d < dimensions; d++) {
+ final DAFile f = new DAFile(relation, d, partitions);
+ splitPartitions[d] = f.getSplitPositions();
+ daFiles.add(f);
+ }
+
+ vectorApprox = new ArrayList<VectorApproximation>();
+ for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
+ DBID id = iter.getDBID();
+ V dv = relation.get(id);
+ VectorApproximation va = calculateFullApproximation(id, dv);
+ vectorApprox.add(va);
+ }
+ }
+
+ @Override
+ public String getShortName() {
+ return "pva-file";
+ }
+
+ @Override
+ public String getLongName() {
+ return "partial va-file";
+ }
+
+ /**
+ * Fake subspace (full-dimensional).
+ *
+ * @param relation Relation with full dimensionality
+ * @return Bit set with all bits set.
+ */
+ protected static BitSet fakeSubspace(Relation<? extends NumberVector<?, ?>> relation) {
+ int dim = DatabaseUtil.dimensionality(relation);
+ BitSet bits = new BitSet();
+ for(int i = 0; i < dim; i++) {
+ bits.set(i);
+ }
+ return bits;
+ }
+
+ /**
+ * Calculate the VA file position given the existing borders.
+ *
+ * @param id Object ID
+ * @param dv Data vector
+ * @return Vector approximation
+ */
+ protected VectorApproximation calculateFullApproximation(DBID id, V dv) {
+ int approximation[] = new int[dv.getDimensionality()];
+ for(int d = 0; d < splitPartitions.length; d++) {
+ double[] split = daFiles.get(d).getSplitPositions();
+ final double val = dv.doubleValue(d + 1);
+ final int lastBorderIndex = split.length - 1;
+
+ // Value is below data grid
+ if(val < split[0]) {
+ approximation[d] = 0;
+ if(id != null) {
+ logger.warning("Vector outside of VAFile grid!");
+ }
+ } // Value is above data grid
+ else if(val > split[lastBorderIndex]) {
+ approximation[d] = lastBorderIndex - 1;
+ if(id != null) {
+ logger.warning("Vector outside of VAFile grid!");
+ }
+ } // normal case
+ else {
+ // Search grid position
+ int pos = Arrays.binarySearch(split, val);
+ pos = (pos >= 0) ? pos : ((-pos) - 2);
+ approximation[d] = pos;
+ }
+ }
+ return new VectorApproximation(id, approximation);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public <D extends Distance<D>> KNNQuery<V, D> getKNNQuery(DistanceQuery<V, D> distanceQuery, Object... hints) {
+ for(Object hint : hints) {
+ if(hint == DatabaseQuery.HINT_BULK) {
+ // FIXME: support bulk?
+ return null;
+ }
+ }
+ DistanceFunction<? super V, ?> df = distanceQuery.getDistanceFunction();
+ if(df instanceof SubspaceLPNormDistanceFunction) {
+ double p = ((SubspaceLPNormDistanceFunction) df).getP();
+ BitSet bits = ((SubspaceLPNormDistanceFunction) df).getSelectedDimensions();
+ DistanceQuery<V, ?> ddq = (DistanceQuery<V, ?>) distanceQuery;
+ KNNQuery<V, ?> dq = new PartialVAFileKNNQuery((DistanceQuery<V, DoubleDistance>) ddq, p, bits);
+ return (KNNQuery<V, D>) dq;
+ }
+ if(df instanceof LPNormDistanceFunction) {
+ double p = ((LPNormDistanceFunction) df).getP();
+ BitSet bits = fakeSubspace(distanceQuery.getRelation());
+ DistanceQuery<V, ?> ddq = (DistanceQuery<V, ?>) distanceQuery;
+ KNNQuery<V, ?> dq = new PartialVAFileKNNQuery((DistanceQuery<V, DoubleDistance>) ddq, p, bits);
+ return (KNNQuery<V, D>) dq;
+ }
+ // Not supported.
+ return null;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public <D extends Distance<D>> RangeQuery<V, D> getRangeQuery(DistanceQuery<V, D> distanceQuery, Object... hints) {
+ DistanceFunction<? super V, ?> df = distanceQuery.getDistanceFunction();
+ if(df instanceof SubspaceLPNormDistanceFunction) {
+ double p = ((SubspaceLPNormDistanceFunction) df).getP();
+ BitSet bits = ((SubspaceLPNormDistanceFunction) df).getSelectedDimensions();
+ DistanceQuery<V, ?> ddq = (DistanceQuery<V, ?>) distanceQuery;
+ RangeQuery<V, ?> dq = new PartialVAFileRangeQuery((DistanceQuery<V, DoubleDistance>) ddq, p, bits);
+ return (RangeQuery<V, D>) dq;
+ }
+ if(df instanceof LPNormDistanceFunction) {
+ double p = ((LPNormDistanceFunction) df).getP();
+ BitSet bits = fakeSubspace(distanceQuery.getRelation());
+ DistanceQuery<V, ?> ddq = (DistanceQuery<V, ?>) distanceQuery;
+ RangeQuery<V, ?> dq = new PartialVAFileRangeQuery((DistanceQuery<V, DoubleDistance>) ddq, p, bits);
+ return (RangeQuery<V, D>) dq;
+ }
+ // Not supported.
+ return null;
+ }
+
+ /**
+ * Calculate selectivity coefficients.
+ *
+ * @param daFiles List of files to use
+ * @param query Query vector
+ * @param epsilon Epsilon radius
+ */
+ protected static void calculateSelectivityCoeffs(List<DoubleObjPair<DAFile>> daFiles, NumberVector<?, ?> query, double epsilon) {
+ final int dimensions = query.getDimensionality();
+ double[] lowerVals = new double[dimensions];
+ double[] upperVals = new double[dimensions];
+
+ VectorApproximation queryApprox = calculatePartialApproximation(null, query, daFiles);
+
+ for(int i = 0; i < dimensions; i++) {
+ lowerVals[i] = query.doubleValue(i + 1) - epsilon;
+ upperVals[i] = query.doubleValue(i + 1) + epsilon;
+ }
+
+ Vector lowerEpsilon = new Vector(lowerVals);
+ VectorApproximation lowerEpsilonPartitions = calculatePartialApproximation(null, lowerEpsilon, daFiles);
+
+ Vector upperEpsilon = new Vector(upperVals);
+ VectorApproximation upperEpsilonPartitions = calculatePartialApproximation(null, upperEpsilon, daFiles);
+
+ for(int i = 0; i < daFiles.size(); i++) {
+ int coeff = (queryApprox.getApproximation(i) - lowerEpsilonPartitions.getApproximation(i)) + (upperEpsilonPartitions.getApproximation(i) - queryApprox.getApproximation(i)) + 1;
+ daFiles.get(i).first = coeff;
+ }
+ }
+
+ /**
+ * Calculate partial vector approximation
+ *
+ * @param id Object ID
+ * @param dv Object vector
+ * @param daFiles List of approximations to use
+ * @return Vector approximation
+ */
+ protected static VectorApproximation calculatePartialApproximation(DBID id, NumberVector<?, ?> dv, List<DoubleObjPair<DAFile>> daFiles) {
+ int[] approximation = new int[dv.getDimensionality()];
+ for(int i = 0; i < daFiles.size(); i++) {
+ double val = dv.doubleValue(i + 1);
+ double[] borders = daFiles.get(i).second.getSplitPositions();
+ assert borders != null : "borders are null";
+ int lastBorderIndex = borders.length - 1;
+
+ // value is lower outlier
+ if(val < borders[0]) {
+ approximation[i] = 0;
+ } // value is upper outlier
+ else if(val > borders[lastBorderIndex]) {
+ approximation[i] = lastBorderIndex - 1;
+ } // normal case
+ else {
+ for(int s = 0; s < lastBorderIndex; s++) {
+ if(val >= borders[s] && val < borders[s + 1] && approximation[i] != -1) {
+ approximation[i] = s;
+ }
+ }
+ }
+ }
+ return new VectorApproximation(id, approximation);
+ }
+
+ /**
+ * Class for tracking Partial VA file statistics
+ *
+ * TODO: refactor into a common statistics API
+ *
+ * @apiviz.exclude
+ */
+ public static class Statistics {
+ public long scannedBytes = 0;
+
+ public long queryTime = 0;
+
+ public int issuedQueries = 0;
+
+ public int refinements = 0;
+ }
+
+ /**
+ * Object in a VA approximation.
+ *
+ * @author Thomas Bernecker
+ * @author Erich Schubert
+ */
+ protected static class PartialVACandidate implements Comparable<PartialVACandidate> {
+ /**
+ * (Current) maximum distance of this candidate.
+ */
+ protected double maxDistP = 0.0;
+
+ /**
+ * (Current) minimum distance of this candidate.
+ */
+ protected double minDistP = 0.0;
+
+ /**
+ * The actual approximation
+ */
+ final private VectorApproximation approx;
+
+ /**
+ *
+ * Constructor.
+ *
+ * @param approx The actual approximation
+ */
+ public PartialVACandidate(VectorApproximation approx) {
+ super();
+ this.approx = approx;
+ }
+
+ public int getApproximation(int dimension) {
+ return approx.getApproximation(dimension);
+ }
+
+ public DBID getId() {
+ return approx.getId();
+ }
+
+ @Override
+ public String toString() {
+ return approx.toString() + ", bounds^p: [" + minDistP + ", " + maxDistP + "]";
+ }
+
+ @Override
+ public int compareTo(PartialVACandidate o) {
+ return Double.compare(this.minDistP, o.minDistP);
+ }
+ }
+
+ /**
+ * Range query for this index.
+ *
+ * @author Erich Schubert
+ * @author Thomas Bernecker
+ */
+ public class PartialVAFileRangeQuery extends AbstractRefiningIndex<V>.AbstractRangeQuery<DoubleDistance> {
+ /**
+ * Lp-Norm p
+ */
+ private double p;
+
+ /**
+ * Subspace
+ */
+ private BitSet subspace;
+
+ /**
+ * Constructor.
+ *
+ * @param ddq Distance query
+ * @param p LP Norm p
+ * @param subspace Subspace
+ */
+ public PartialVAFileRangeQuery(DistanceQuery<V, DoubleDistance> ddq, double p, BitSet subspace) {
+ super(ddq);
+ this.p = p;
+ this.subspace = subspace;
+ }
+
+ @Override
+ public DistanceDBIDResult<DoubleDistance> getRangeForObject(V query, DoubleDistance range) {
+ stats.issuedQueries++;
+ long t = System.nanoTime();
+
+ final double epsilonP = Math.pow(range.doubleValue(), p);
+
+ // generate query approximation and lookup table
+ final VectorApproximation queryApprox = calculateFullApproximation(null, query);
+ final VALPNormDistance dist = new VALPNormDistance(p, splitPartitions, query, queryApprox);
+
+ // perform multi-step range query
+
+ // filter step
+
+ // calculate selectivity coefficients
+ List<DoubleObjPair<DAFile>> subspaceDAFiles = new ArrayList<DoubleObjPair<DAFile>>(subspace.cardinality());
+ for(int d = subspace.nextSetBit(0); d >= 0; d = subspace.nextSetBit(d + 1)) {
+ DAFile daFile = daFiles.get(d);
+ subspaceDAFiles.add(new DoubleObjPair<DAFile>(-1, daFile));
+ }
+ calculateSelectivityCoeffs(subspaceDAFiles, query, range.doubleValue());
+ // sort DA files by selectivity
+ // TODO: validate that this is the correct order
+ Collections.sort(subspaceDAFiles, Collections.reverseOrder());
+
+ // create candidate list (all objects) and prune candidates w.r.t.
+ // mindist (i.e. remove them from the list)
+ // important: this structure contains the maxDist values for refinement!
+ DistanceDBIDResult<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>();
+ int candidates = 0;
+ for(VectorApproximation va : vectorApprox) {
+ DBID id = va.getId();
+ PartialVACandidate pva = new PartialVACandidate(va);
+
+ boolean pruned = false;
+ for(DoubleObjPair<DAFile> da : subspaceDAFiles) {
+ int dimension = da.second.getDimension();
+ int objectCell = va.getApproximation(dimension);
+ pva.minDistP += dist.getPartialMinDist(dimension, objectCell);
+ pva.maxDistP += dist.getPartialMaxDist(dimension, objectCell);
+ if(pva.minDistP > epsilonP) {
+ pruned = true;
+ break;
+ }
+ }
+ if(!pruned) {
+ candidates++;
+ if(pva.maxDistP <= epsilonP) {
+ // candidate cannot be dropped
+ // TODO: actually: no refinement needed - need API that allows
+ // reporting maxdists only.
+ result.add(new DoubleDistanceResultPair(refine(id, query).doubleValue(), id));
+ }
+ else { // refine candidate - true refinement
+ DoubleDistance dis = refine(id, query);
+ stats.refinements += 1;
+ if(dis.doubleValue() <= range.doubleValue()) {
+ result.add(new DoubleDistanceResultPair(dis.doubleValue(), id));
+ }
+ }
+ }
+ }
+ Collections.sort(result);
+
+ stats.scannedBytes += relation.size() * VectorApproximation.byteOnDisk(subspace.cardinality(), partitions);
+
+ stats.queryTime += System.nanoTime() - t;
+
+ if(logger.isDebuggingFine()) {
+ logger.fine("query = " + query);
+ logger.fine("database: " + relation.size() + ", candidates: " + candidates + ", results: " + result.size());
+ }
+
+ return result;
+ }
+ }
+
+ /**
+ * KNN query for this index.
+ *
+ * @author Erich Schubert
+ * @author Thomas Bernecker
+ */
+ public class PartialVAFileKNNQuery extends AbstractRefiningIndex<V>.AbstractKNNQuery<DoubleDistance> {
+ /**
+ * Lp-Norm p
+ */
+ private double p;
+
+ /**
+ * Subspace
+ */
+ private BitSet subspace;
+
+ /**
+ * Constructor.
+ *
+ * @param ddq Distance query
+ * @param p LP-norm p
+ * @param subspace Subspace to query
+ */
+ public PartialVAFileKNNQuery(DistanceQuery<V, DoubleDistance> ddq, double p, BitSet subspace) {
+ super(ddq);
+ this.p = p;
+ this.subspace = subspace;
+ }
+
+ @Override
+ public KNNResult<DoubleDistance> getKNNForObject(V query, int k) {
+ stats.issuedQueries++;
+ long t = System.nanoTime();
+
+ // generate query approximation and lookup table
+ VectorApproximation queryApprox = calculateFullApproximation(null, query);
+ final VALPNormDistance dist = new VALPNormDistance(p, splitPartitions, query, queryApprox);
+
+ // sort DA files by worst case distance
+ List<DAFile> daFiles = getWorstCaseDistOrder(dist, subspace);
+
+ final int currentSubspaceDims = subspace.cardinality();
+ int reducedDims = (2 * currentSubspaceDims) / 3;
+ reducedDims = Math.max(1, reducedDims);
+ if(logger.isDebuggingFine()) {
+ logger.fine("subspaceDims=" + currentSubspaceDims + ", reducedDims=" + reducedDims);
+ }
+
+ // filter 1
+ LinkedList<PartialVACandidate> candidates1 = filter1(k, reducedDims, daFiles, queryApprox, currentSubspaceDims, dist);
+ if(logger.isDebuggingFine()) {
+ logger.fine("candidate set after filter 1: " + candidates1.size());
+ }
+
+ // filters 2+
+ LinkedList<PartialVACandidate> candidates2 = null;
+ int addition = reducedDims;
+ int filterStep = 2;
+
+ if(currentSubspaceDims <= reducedDims) {
+ candidates2 = candidates1;
+ }
+ else {
+ // continue filtering until I/O costs of refining candidates < I/O
+ // costs of loading new DA files
+ while(candidates2 == null || (getIOCosts(candidates2.size(), currentSubspaceDims) >= getIOCosts(daFiles.get(0), currentSubspaceDims - addition)) && addition < currentSubspaceDims) {
+ if(candidates2 != null && logger.isDebuggingFine()) {
+ logger.fine("filter " + filterStep + ": refining costs " + getIOCosts(candidates2.size(), currentSubspaceDims) + " (" + candidates2.size() + "/" + currentSubspaceDims + "), DA file costs " + getIOCosts(daFiles.get(0), currentSubspaceDims - addition) + " (dim " + (addition + 1) + " of " + currentSubspaceDims + ")");
+ }
+ if(candidates2 != null) {
+ candidates1 = candidates2;
+ }
+ candidates2 = new LinkedList<PartialVACandidate>();
+
+ Heap<Double> kMinMaxDists = new TopBoundedHeap<Double>(k, Collections.reverseOrder());
+ for(PartialVACandidate va : candidates1) {
+ int dimension = daFiles.get(addition).getDimension();
+ int objectCell = va.getApproximation(dimension);
+
+ va.minDistP += dist.getPartialMinDist(dimension, objectCell);
+ va.maxDistP += dist.getPartialMaxDist(dimension, objectCell) - dist.getPartialMaxMaxDist(dimension);
+
+ if(kMinMaxDists.size() < k || va.minDistP <= kMinMaxDists.peek()) {
+ candidates2.add(va);
+ kMinMaxDists.add(va.maxDistP);
+ }
+ }
+
+ if(logger.isDebuggingFine()) {
+ logger.fine("candidate set after filter " + filterStep + ": " + candidates2.size());
+ }
+
+ addition++;
+ filterStep++;
+ }
+ }
+
+ stats.scannedBytes += relation.size() * VectorApproximation.byteOnDisk(addition, partitions);
+
+ // refinement step
+ ArrayList<PartialVACandidate> sortedCandidates = new ArrayList<PartialVACandidate>(candidates2);
+ // sort candidates by lower bound (minDist)
+ Collections.sort(sortedCandidates);
+ KNNList<DoubleDistance> result = retrieveAccurateDistances(sortedCandidates, k, subspace, query);
+
+ stats.queryTime += System.nanoTime() - t;
+ return result;
+ }
+
+ private LinkedList<PartialVACandidate> filter1(int k, int reducedDims, List<DAFile> daFiles, VectorApproximation queryApprox, int subspaceDims, VALPNormDistance dist) {
+ LinkedList<PartialVACandidate> candidates1 = new LinkedList<PartialVACandidate>();
+ Heap<Double> minmaxdist = new TopBoundedHeap<Double>(k, Collections.reverseOrder());
+
+ for(VectorApproximation va : vectorApprox) {
+ PartialVACandidate pva = new PartialVACandidate(va);
+ for(int d = 0; d < reducedDims; d++) {
+ int dimension = daFiles.get(d).getDimension();
+ int objectCell = pva.getApproximation(dimension);
+ pva.minDistP += dist.getPartialMinDist(dimension, objectCell);
+ pva.maxDistP += dist.getPartialMaxDist(dimension, objectCell);
+ }
+ for(int d = reducedDims; d < subspaceDims; d++) {
+ pva.maxDistP += dist.getPartialMaxMaxDist(daFiles.get(d).getDimension());
+ }
+ if(minmaxdist.size() < k || pva.minDistP <= minmaxdist.peek()) {
+ candidates1.add(pva);
+ minmaxdist.add(pva.maxDistP);
+ }
+ }
+ // Drop candidates that don't satisfy the latest minmaxdist
+ final double minmax = minmaxdist.peek();
+ Iterator<PartialVACandidate> it = candidates1.iterator();
+ while(it.hasNext()) {
+ PartialVACandidate pva = it.next();
+ if(pva.minDistP > minmax) {
+ it.remove();
+ }
+ }
+
+ return candidates1;
+ }
+
+ /**
+ * Computes IO costs (in bytes) needed for refining the candidates.
+ *
+ * @param size The nuber of candidates
+ * @param subspaceDims the required subspace dimensions
+ * @return the cost value (in bytes)
+ */
+ private int getIOCosts(int size, int subspaceDims) {
+ return size * (subspaceDims * 8 + 4);
+ }
+
+ /**
+ * Computes IO costs (in bytes) needed for reading several DA-files.
+ *
+ * @param sample the DA-file specific costs
+ * @param numberOfDAFiles the number of DA-files that have to be read
+ * @return the cost value (in bytes)
+ */
+ private int getIOCosts(DAFile sample, int numberOfDAFiles) {
+ return sample.getIOCosts() * numberOfDAFiles;
+ }
+
+ /**
+ * Order subspaces by their worst case distance.
+ *
+ * @param dist Distance function
+ * @param subspace Subspace
+ * @return Ordered list of dimension files
+ */
+ public List<DAFile> getWorstCaseDistOrder(VALPNormDistance dist, BitSet subspace) {
+ int subspaceLength = subspace.cardinality();
+ List<DAFile> result = new ArrayList<DAFile>(subspaceLength);
+ for(int i = subspace.nextSetBit(0); i >= 0; i = subspace.nextSetBit(i + 1)) {
+ result.add(daFiles.get(i));
+ }
+ Collections.sort(result, new WorstCaseDistComparator(dist));
+ return result;
+ }
+
+ protected KNNList<DoubleDistance> retrieveAccurateDistances(List<PartialVACandidate> sortedCandidates, int k, BitSet subspace, V query) {
+ KNNHeap<DoubleDistance> result = new KNNHeap<DoubleDistance>(k, DoubleDistance.FACTORY.infiniteDistance());
+ for(PartialVACandidate va : sortedCandidates) {
+ double stopdist = result.getKNNDistance().doubleValue();
+ DBID currentID = va.getId();
+ if(result.size() < k || va.minDistP < stopdist) {
+ DoubleDistance dist = refine(currentID, query);
+ stats.refinements += 1;
+ if(dist.doubleValue() < stopdist) {
+ result.add(new DoubleDistanceResultPair(dist.doubleValue(), currentID));
+ }
+ }
+ }
+ return result.toKNNList();
+ }
+ }
+
+ /**
+ * Compare DAfiles by their worst case distance.
+ *
+ * @apiviz.exclude
+ */
+ protected static class WorstCaseDistComparator implements Comparator<DAFile> {
+ private VALPNormDistance dist;
+
+ public WorstCaseDistComparator(VALPNormDistance dist) {
+ this.dist = dist;
+ }
+
+ @Override
+ public int compare(DAFile a, DAFile b) {
+ return Double.compare(dist.getPartialMaxMaxDist(a.getDimension()), dist.getPartialMaxMaxDist(b.getDimension()));
+ }
+ }
+
+ /**
+ * Index factory class
+ *
+ * @author Erich Schubert
+ *
+ * @apiviz.stereotype «factory»
+ * @apiviz.has PartialVAFile
+ *
+ * @param <V> Vector type
+ */
+ public static class Factory<V extends NumberVector<?, ?>> implements IndexFactory<V, PartialVAFile<V>> {
+ /**
+ * Number of partitions to use in each dimension.
+ *
+ * <pre>
+ * -vafile.partitions 8
+ * </pre>
+ */
+ public static final OptionID PARTITIONS_ID = OptionID.getOrCreateOptionID("vafile.partitions", "Number of partitions to use in each dimension.");
+
+ /**
+ * Page size
+ */
+ int pagesize = 1;
+
+ /**
+ * Number of partitions
+ */
+ int numpart = 2;
+
+ /**
+ * Constructor.
+ *
+ * @param pagesize Page size
+ * @param numpart Number of partitions
+ */
+ public Factory(int pagesize, int numpart) {
+ super();
+ this.pagesize = pagesize;
+ this.numpart = numpart;
+ }
+
+ @Override
+ public PartialVAFile<V> instantiate(Relation<V> relation) {
+ return new PartialVAFile<V>(pagesize, relation, numpart);
+ }
+
+ @Override
+ public TypeInformation getInputTypeRestriction() {
+ return TypeUtil.NUMBER_VECTOR_FIELD;
+ }
+
+ /**
+ * Parameterization class
+ *
+ * @author Erich Schubert
+ *
+ * @apiviz.exclude
+ */
+ public static class Parameterizer extends AbstractParameterizer {
+ /**
+ * Page size
+ */
+ int pagesize = 1;
+
+ /**
+ * Number of partitions
+ */
+ int numpart = 2;
+
+ @Override
+ protected void makeOptions(Parameterization config) {
+ super.makeOptions(config);
+ IntParameter pagesizeP = new IntParameter(TreeIndexFactory.PAGE_SIZE_ID, new GreaterConstraint(0), 1024);
+ if(config.grab(pagesizeP)) {
+ pagesize = pagesizeP.getValue();
+ }
+ IntParameter partitionsP = new IntParameter(Factory.PARTITIONS_ID, new GreaterConstraint(2));
+ if(config.grab(partitionsP)) {
+ numpart = partitionsP.getValue();
+ }
+ }
+
+ @Override
+ protected Factory<?> makeInstance() {
+ return new Factory<NumberVector<?, ?>>(pagesize, numpart);
+ }
+ }
+ }
+}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/vafile/VAFile.java b/src/de/lmu/ifi/dbs/elki/index/vafile/VAFile.java index c426c1d6..1d4f8f6d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/vafile/VAFile.java +++ b/src/de/lmu/ifi/dbs/elki/index/vafile/VAFile.java @@ -32,10 +32,12 @@ import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.type.TypeInformation;
import de.lmu.ifi.dbs.elki.data.type.TypeUtil;
import de.lmu.ifi.dbs.elki.database.ids.DBID;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery;
-import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair;
+import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult;
import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair;
+import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList;
import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery;
import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult;
@@ -76,6 +78,13 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; *
* @author Thomas Bernecker
* @author Erich Schubert
+ *
+ * @apiviz.landmark
+ *
+ * @apiviz.composedOf VectorApproximation
+ * @apiviz.has VAFileRangeQuery
+ * @apiviz.has VAFileKNNQuery
+ * @apiviz.uses VALPNormDistance
*/
@Title("An approximation based data structure for similarity search")
@Reference(authors = "Weber, R. and Blott, S.", title = "An approximation based data structure for similarity search", booktitle = "Report TR1997b, ETH Zentrum, Zurich, Switzerland", url = "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.480&rep=rep1&type=pdf")
@@ -128,7 +137,8 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< @Override
protected void initialize(Relation<V> relation, DBIDs ids) {
setPartitions(relation);
- for(DBID id : relation.getDBIDs()) {
+ for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
+ DBID id = iter.getDBID();
vectorApprox.add(calculateApproximation(id, relation.get(id)));
}
}
@@ -151,7 +161,8 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< for(int d = 0; d < dimensions; d++) {
double[] tempdata = new double[size];
int j = 0;
- for(DBID id : relation.iterDBIDs()) {
+ for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { + DBID id = iditer.getDBID();
tempdata[j] = relation.get(id).doubleValue(d + 1);
j += 1;
}
@@ -288,7 +299,7 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< *
* @author Erich Schubert
*/
- class VAFileRangeQuery extends AbstractRefiningIndex<V>.AbstractRangeQuery<DoubleDistance> {
+ public class VAFileRangeQuery extends AbstractRefiningIndex<V>.AbstractRangeQuery<DoubleDistance> {
/**
* LP Norm p parameter.
*/
@@ -307,7 +318,7 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< }
@Override
- public List<DistanceResultPair<DoubleDistance>> getRangeForObject(V query, DoubleDistance range) {
+ public DistanceDBIDResult<DoubleDistance> getRangeForObject(V query, DoubleDistance range) {
final double eps = range.doubleValue();
// generate query approximation and lookup table
VectorApproximation queryApprox = calculateApproximation(null, query);
@@ -318,7 +329,7 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< // Count a VA file scan
scans += 1;
- List<DistanceResultPair<DoubleDistance>> result = new ArrayList<DistanceResultPair<DoubleDistance>>();
+ GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>();
// Approximation step
for(int i = 0; i < vectorApprox.size(); i++) {
VectorApproximation va = vectorApprox.get(i);
@@ -347,7 +358,7 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< *
* @author Erich Schubert
*/
- class VAFileKNNQuery extends AbstractRefiningIndex<V>.AbstractKNNQuery<DoubleDistance> {
+ public class VAFileKNNQuery extends AbstractRefiningIndex<V>.AbstractKNNQuery<DoubleDistance> {
/**
* LP Norm p parameter.
*/
@@ -434,6 +445,9 @@ public class VAFile<V extends NumberVector<?, ?>> extends AbstractRefiningIndex< *
* @author Erich Schubert
*
+ * @apiviz.stereotype «factory»
+ * @apiviz.has VAFile
+ *
* @param <V> Vector type
*/
public static class Factory<V extends NumberVector<?, ?>> implements IndexFactory<V, VAFile<V>> {
|