summaryrefslogtreecommitdiff
path: root/src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java')
-rw-r--r--src/de/lmu/ifi/dbs/elki/index/preprocessed/knn/MaterializeKNNAndRKNNPreprocessor.java37
1 files changed, 19 insertions, 18 deletions
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 9abd4a74..1436efe2 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
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed.knn;
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
- Copyright (C) 2011
+ Copyright (C) 2012
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
@@ -34,13 +34,15 @@ 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.ArrayDBIDs;
+import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs;
import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
-import de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs;
+import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs;
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;
+import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult;
import de.lmu.ifi.dbs.elki.database.query.rknn.PreprocessorRKNNQuery;
import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
@@ -51,6 +53,7 @@ import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.logging.progress.FiniteProgress;
import de.lmu.ifi.dbs.elki.logging.progress.StepProgress;
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.documentation.Description;
import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
@@ -88,7 +91,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
@Override
protected void preprocess() {
- storage = DataStoreUtil.makeStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT, List.class);
+ createStorage();
materialized_RkNN = DataStoreUtil.makeStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT, Set.class);
FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("Materializing k nearest neighbors and reverse k nearest neighbors (k=" + k + ")", relation.size(), getLogger()) : null;
materializeKNNAndRKNNs(DBIDUtil.ensureArray(relation.getDBIDs()), progress);
@@ -100,7 +103,6 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
* @param ids the IDs of the objects
*/
private void materializeKNNAndRKNNs(ArrayDBIDs ids, FiniteProgress progress) {
-
// add an empty list to each rknn
for(DBID id : ids) {
if(materialized_RkNN.get(id) == null) {
@@ -109,10 +111,10 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
}
// knn query
- List<List<DistanceResultPair<D>>> kNNList = knnQuery.getKNNForBulkDBIDs(ids, k);
+ List<KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(ids, k);
for(int i = 0; i < ids.size(); i++) {
DBID id = ids.get(i);
- List<DistanceResultPair<D>> kNNs = kNNList.get(i);
+ KNNResult<D> kNNs = kNNList.get(i);
storage.put(id, kNNs);
for(DistanceResultPair<D> kNN : kNNs) {
Set<DistanceResultPair<D>> rknns = materialized_RkNN.get(kNN.getDBID());
@@ -165,13 +167,12 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
* updated
*/
private ArrayDBIDs updateKNNsAndRkNNs(DBIDs ids) {
- ArrayDBIDs rkNN_ids = DBIDUtil.newArray();
+ ArrayModifiableDBIDs rkNN_ids = DBIDUtil.newArray();
DBIDs oldids = DBIDUtil.difference(relation.getDBIDs(), ids);
for(DBID id1 : oldids) {
- List<DistanceResultPair<D>> kNNs = storage.get(id1);
- D knnDist = kNNs.get(kNNs.size() - 1).getDistance();
+ KNNResult<D> kNNs = storage.get(id1);
+ D knnDist = kNNs.getKNNDistance();
// look for new kNNs
- List<DistanceResultPair<D>> newKNNs = new ArrayList<DistanceResultPair<D>>();
KNNHeap<D> heap = null;
for(DBID id2 : ids) {
D dist = distanceQuery.distance(id1, id2);
@@ -184,7 +185,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
}
}
if(heap != null) {
- newKNNs = heap.toSortedArrayList();
+ KNNList<D> newKNNs = heap.toKNNList();
storage.put(id1, newKNNs);
// get the difference
@@ -234,7 +235,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
if(stepprog != null) {
stepprog.beginStep(1, "New deletions ocurred, remove their materialized kNNs and RkNNs.", getLogger());
}
- List<List<DistanceResultPair<D>>> kNNs = new ArrayList<List<DistanceResultPair<D>>>(ids.size());
+ 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));
@@ -250,7 +251,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
stepprog.beginStep(2, "New deletions ocurred, update the affected kNNs and RkNNs.", getLogger());
}
// update the kNNs of the RkNNs
- List<List<DistanceResultPair<D>>> kNNList = knnQuery.getKNNForBulkDBIDs(rkNN_ids, k);
+ List<KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(rkNN_ids, k);
for(int i = 0; i < rkNN_ids.size(); i++) {
DBID id = rkNN_ids.get(i);
storage.put(id, kNNList.get(i));
@@ -260,7 +261,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
}
}
// update the RkNNs of the kNNs
- TreeSetDBIDs idsSet = DBIDUtil.newTreeSet(ids);
+ SetDBIDs idsSet = DBIDUtil.ensureSet(ids);
for(int i = 0; i < kNN_ids.size(); i++) {
DBID id = kNN_ids.get(i);
SortedSet<DistanceResultPair<D>> rkNN = materialized_RkNN.get(id);
@@ -289,7 +290,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
* @param id the query id
* @return the kNNs
*/
- public List<DistanceResultPair<D>> getKNN(DBID id) {
+ public KNNResult<D> getKNN(DBID id) {
return storage.get(id);
}
@@ -333,7 +334,7 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
public String getShortName() {
return "knn and rknn preprocessor";
}
-
+
@Override
protected Logging getLogger() {
return logger;
@@ -373,8 +374,8 @@ public class MaterializeKNNAndRKNNPreprocessor<O, D extends Distance<D>> extends
*/
public static class Parameterizer<O, D extends Distance<D>> extends MaterializeKNNPreprocessor.Factory.Parameterizer<O, D> {
@Override
- protected Factory<O,D> makeInstance() {
- return new Factory<O,D>(k, distanceFunction);
+ protected Factory<O, D> makeInstance() {
+ return new Factory<O, D>(k, distanceFunction);
}
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-29 12:01:01 +0000