diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query')
4 files changed, 48 insertions, 66 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 f0acc233..6d539f25 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 @@ -38,11 +38,11 @@ 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; -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.distanceresultlist.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNList; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -51,7 +51,6 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; 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.documentation.Reference; /** @@ -102,8 +101,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param object the query object * @param knnList the knn list containing the result */ - protected void doKNNQuery(O object, KNNHeap<DoubleDistance> knnList) { - final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() * 2, 20)); + protected void doKNNQuery(O object, DoubleDistanceKNNHeap knnList) { + final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() << 1, 20)); // push root pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID())); @@ -120,7 +119,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } } - private double expandNode(O object, KNNHeap<DoubleDistance> knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final Integer nodeID) { + private double expandNode(O object, DoubleDistanceKNNHeap knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { @@ -129,8 +128,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend double distance = distanceFunction.doubleMinDist(entry, object); tree.distanceCalcs++; if(distance <= maxDist) { - knnList.add(new DoubleDistanceResultPair(distance, ((LeafEntry) entry).getDBID())); - maxDist = knnList.getKNNDistance().doubleValue(); + knnList.add(distance, ((LeafEntry) entry).getDBID()); + maxDist = knnList.doubleKNNDistance(); } } } @@ -160,20 +159,20 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param node the node for which the query should be performed * @param knnLists a map containing the knn lists for each query objects */ - protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap<DoubleDistance>> knnLists) { + protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, DoubleDistanceKNNHeap> knnLists) { if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry p = node.getEntry(i); - for(Entry<DBID, KNNHeap<DoubleDistance>> ent : knnLists.entrySet()) { + for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { final DBID q = ent.getKey(); - final KNNHeap<DoubleDistance> knns_q = ent.getValue(); - DoubleDistance knn_q_maxDist = knns_q.getKNNDistance(); + final DoubleDistanceKNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.doubleKNNDistance(); DBID pid = ((LeafEntry) p).getDBID(); // FIXME: objects are NOT accessible by DBID in a plain rtree context! - DoubleDistance dist_pq = distanceFunction.distance(relation.get(pid), relation.get(q)); + double dist_pq = distanceFunction.doubleDistance(relation.get(pid), relation.get(q)); tree.distanceCalcs++; - if(dist_pq.compareTo(knn_q_maxDist) <= 0) { + if(dist_pq <= knn_q_maxDist) { knns_q.add(dist_pq, pid); } } @@ -187,13 +186,13 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend List<DoubleDistanceEntry> entries = getSortedEntries(node, ids); for(DoubleDistanceEntry distEntry : entries) { double minDist = distEntry.distance; - for(Entry<DBID, KNNHeap<DoubleDistance>> ent : knnLists.entrySet()) { - final KNNHeap<DoubleDistance> knns_q = ent.getValue(); - double knn_q_maxDist = knns_q.getKNNDistance().doubleValue(); + for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { + final DoubleDistanceKNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.doubleKNNDistance(); if(minDist <= knn_q_maxDist) { SpatialEntry entry = distEntry.entry; - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID()); + AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; } @@ -264,47 +263,41 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } @Override - public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { + public DoubleDistanceKNNList 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()); + final DoubleDistanceKNNHeap knnList = new DoubleDistanceKNNHeap(k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @Override - public KNNResult<DoubleDistance> getKNNForDBID(DBIDRef id, int k) { + public DoubleDistanceKNNList getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<KNNResult<DoubleDistance>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<DoubleDistanceKNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(k < 1) { throw new IllegalArgumentException("At least one enumeration has to be requested!"); } // 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()); + final Map<DBID, DoubleDistanceKNNHeap> knnLists = new HashMap<DBID, DoubleDistanceKNNHeap>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - knnLists.put(id, new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + DBID id = DBIDUtil.deref(iter); + knnLists.put(id, new DoubleDistanceKNNHeap(k)); } batchNN(tree.getRoot(), knnLists); - List<KNNResult<DoubleDistance>> result = new ArrayList<KNNResult<DoubleDistance>>(); + List<DoubleDistanceKNNList> result = new ArrayList<DoubleDistanceKNNList>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); result.add(knnLists.get(id).toKNNList()); } return result; } - - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<DoubleDistance>> heaps) { - AbstractRStarTreeNode<?, ?> root = tree.getRoot(); - batchNN(root, heaps); - } }
\ No newline at end of file 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 1a861c3e..715b9552 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,16 +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.Collections; - import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; 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; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -90,8 +87,8 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte * @param epsilon Query range * @return Objects contained in query range. */ - protected GenericDistanceDBIDList<DoubleDistance> doRangeQuery(O object, double epsilon) { - final GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + protected DoubleDistanceDBIDList doRangeQuery(O object, double epsilon) { + final DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(); // push root @@ -104,7 +101,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { @@ -113,7 +110,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte if(distance <= epsilon) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(new DoubleDistanceResultPair(distance, entry.getDBID())); + result.add(distance, entry.getDBID()); } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); @@ -124,7 +121,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte } // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } 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 09ebb61a..ed7f5949 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 @@ -40,9 +40,11 @@ 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.distance.SpatialDistanceQuery; 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.DistanceUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.DistanceEntry; @@ -52,7 +54,6 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; 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.documentation.Reference; /** @@ -103,7 +104,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis * @param knnList the knn list containing the result */ protected void doKNNQuery(O object, KNNHeap<D> knnList) { - final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(Math.min(knnList.getK() * 2, 20)); + final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(Math.min(knnList.getK() << 1, 20)); // push root pq.add(new GenericDistanceSearchCandidate<D>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); @@ -120,7 +121,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } } - private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final Integer nodeID) { + private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { @@ -192,7 +193,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis if(minDist.compareTo(knn_q_maxDist) <= 0) { SpatialEntry entry = distEntry.getEntry(); - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID()); + AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; } @@ -201,12 +202,6 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } } - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - AbstractRStarTreeNode<?, ?> root = tree.getRoot(); - batchNN(root, heaps); - } - /** * Sorts the entries of the specified node according to their minimum distance * to the specified objects. @@ -238,7 +233,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis throw new IllegalArgumentException("At least one enumeration has to be requested!"); } - final KNNHeap<D> knnList = new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance()); + final KNNHeap<D> knnList = KNNUtil.newHeap(distanceFunction, k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @@ -256,14 +251,14 @@ 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 (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - knnLists.put(iter.getDBID(), new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + knnLists.put(DBIDUtil.deref(iter), KNNUtil.newHeap(distanceFunction, k)); } batchNN(tree.getRoot(), knnLists); List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - result.add(knnLists.get(iter.getDBID()).toKNNList()); + result.add(knnLists.get(DBIDUtil.deref(iter)).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 3b312ed7..a5232b30 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,16 +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.Collections; - import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; 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; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -89,7 +86,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D * @param epsilon Query range * @return Objects contained in query range. */ - protected GenericDistanceDBIDList<D> doRangeQuery(O object, D epsilon) { + protected DistanceDBIDResult<D> doRangeQuery(O object, D epsilon) { final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(); @@ -103,7 +100,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { @@ -111,7 +108,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D if(distance.compareTo(epsilon) <= 0) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(new GenericDistanceResultPair<D>(distance, entry.getDBID())); + result.add(distance, entry.getDBID()); } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); @@ -122,7 +119,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D } // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } |