summaryrefslogtreecommitdiff
path: root/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java')
-rw-r--r--src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java89
1 files changed, 52 insertions, 37 deletions
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 7d39c08f..9174dc94 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
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query;
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
@@ -36,10 +36,10 @@ 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.ModifiableDBIDs;
-import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair;
import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair;
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;
import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction;
import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry;
@@ -50,16 +50,24 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree;
import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode;
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.UpdatableHeap;
+import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
/**
* Instance of a KNN query for a particular spatial index.
*
+ * Reference:
+ * <p>
+ * G. R. Hjaltason, H. Samet<br />
+ * Ranking in spatial databases<br />
+ * In: 4th Symposium on Advances in Spatial Databases, SSD'95
+ * </p>
+ *
* @author Erich Schubert
*
* @apiviz.uses AbstractRStarTree
* @apiviz.uses SpatialPrimitiveDoubleDistanceFunction
*/
+@Reference(authors = "G. R. Hjaltason, H. Samet", title = "Ranking in spatial databases", booktitle = "Advances in Spatial Databases - 4th Symposium, SSD'95", url = "http://dx.doi.org/10.1007/3-540-60159-7_6")
public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extends AbstractDistanceKNNQuery<O, DoubleDistance> {
/**
* The index to use
@@ -93,7 +101,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
* @param knnList the knn list containing the result
*/
protected void doKNNQuery(O object, KNNHeap<DoubleDistance> knnList) {
- final Heap<DoubleDistanceSearchCandidate> pq = new UpdatableHeap<DoubleDistanceSearchCandidate>();
+ final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() * 2, 20));
// push root
pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID()));
@@ -106,32 +114,42 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
if(pqNode.mindist > maxDist) {
return;
}
+ maxDist = expandNode(object, knnList, pq, maxDist, pqNode.nodeID);
+ }
+ }
- AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID);
- // data node
- if(node.isLeaf()) {
- for(int i = 0; i < node.getNumEntries(); i++) {
- SpatialEntry entry = node.getEntry(i);
- double distance = distanceFunction.doubleMinDist(entry, object);
- tree.distanceCalcs++;
- if(distance <= maxDist) {
- knnList.add(new DoubleDistanceResultPair(distance, ((LeafEntry) entry).getDBID()));
- maxDist = knnList.getKNNDistance().doubleValue();
- }
+ private double expandNode(O object, KNNHeap<DoubleDistance> knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final Integer nodeID) {
+ AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID);
+ // data node
+ if(node.isLeaf()) {
+ for(int i = 0; i < node.getNumEntries(); i++) {
+ SpatialEntry entry = node.getEntry(i);
+ double distance = distanceFunction.doubleMinDist(entry, object);
+ tree.distanceCalcs++;
+ if(distance <= maxDist) {
+ knnList.add(new DoubleDistanceResultPair(distance, ((LeafEntry) entry).getDBID()));
+ maxDist = knnList.getKNNDistance().doubleValue();
}
}
- // directory node
- else {
- for(int i = 0; i < node.getNumEntries(); i++) {
- SpatialEntry entry = node.getEntry(i);
- double distance = distanceFunction.doubleMinDist(entry, object);
- tree.distanceCalcs++;
+ }
+ // directory node
+ else {
+ for(int i = 0; i < node.getNumEntries(); i++) {
+ SpatialEntry entry = node.getEntry(i);
+ double distance = distanceFunction.doubleMinDist(entry, object);
+ tree.distanceCalcs++;
+ // Greedy expand, bypassing the queue
+ if(distance <= 0) {
+ expandNode(object, knnList, pq, maxDist, ((DirectoryEntry) entry).getPageID());
+ }
+ else {
if(distance <= maxDist) {
- pq.add(new DoubleDistanceSearchCandidate(distance, ((DirectoryEntry)entry).getPageID()));
+ pq.add(new DoubleDistanceSearchCandidate(distance, ((DirectoryEntry) entry).getPageID()));
}
}
}
}
+ return maxDist;
}
/**
@@ -161,7 +179,9 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
}
else {
ModifiableDBIDs ids = DBIDUtil.newArray(knnLists.size());
- ids.addAll(knnLists.keySet());
+ for(DBID id : knnLists.keySet()) {
+ ids.add(id);
+ }
List<DoubleDistanceEntry> entries = getSortedEntries(node, ids);
for(DoubleDistanceEntry distEntry : entries) {
double minDist = distEntry.distance;
@@ -171,7 +191,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
if(minDist <= knn_q_maxDist) {
SpatialEntry entry = distEntry.entry;
- AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry)entry).getPageID());
+ AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID());
batchNN(child, knnLists);
break;
}
@@ -210,7 +230,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
* Optimized double distance entry implementation.
*
* @author Erich Schubert
- *
+ *
* @apiviz.hidden
*/
class DoubleDistanceEntry implements Comparable<DoubleDistanceEntry> {
@@ -226,7 +246,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
/**
* Constructor.
- *
+ *
* @param entry Entry
* @param distance Distance
*/
@@ -242,23 +262,23 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
}
@Override
- public List<DistanceResultPair<DoubleDistance>> getKNNForObject(O obj, int k) {
+ public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) {
if(k < 1) {
throw new IllegalArgumentException("At least one enumeration has to be requested!");
}
final KNNHeap<DoubleDistance> knnList = new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance());
doKNNQuery(obj, knnList);
- return knnList.toSortedArrayList();
+ return knnList.toKNNList();
}
@Override
- public List<DistanceResultPair<DoubleDistance>> getKNNForDBID(DBID id, int k) {
+ public KNNResult<DoubleDistance> getKNNForDBID(DBID id, int k) {
return getKNNForObject(relation.get(id), k);
}
@Override
- public List<List<DistanceResultPair<DoubleDistance>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
+ public List<KNNResult<DoubleDistance>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) {
if(k < 1) {
throw new IllegalArgumentException("At least one enumeration has to be requested!");
}
@@ -271,9 +291,9 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
batchNN(tree.getRoot(), knnLists);
- List<List<DistanceResultPair<DoubleDistance>>> result = new ArrayList<List<DistanceResultPair<DoubleDistance>>>();
+ List<KNNResult<DoubleDistance>> result = new ArrayList<KNNResult<DoubleDistance>>();
for(DBID id : ids) {
- result.add(knnLists.get(id).toSortedArrayList());
+ result.add(knnLists.get(id).toKNNList());
}
return result;
}
@@ -283,9 +303,4 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend
AbstractRStarTreeNode<?, ?> root = tree.getRoot();
batchNN(root, heaps);
}
-
- @Override
- public DoubleDistance getDistanceFactory() {
- return distanceQuery.getDistanceFactory();
- }
} \ No newline at end of file
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-17 17:45:27 +0000