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) 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 .
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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;
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;
import de.lmu.ifi.dbs.elki.index.tree.LeafEntry;
import de.lmu.ifi.dbs.elki.index.tree.query.DoubleDistanceSearchCandidate;
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;
/**
* Instance of a KNN query for a particular spatial index.
*
* Reference:
*
* G. R. Hjaltason, H. Samet
* Ranking in spatial databases
* In: 4th Symposium on Advances in Spatial Databases, SSD'95
*
*
* @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 extends AbstractDistanceKNNQuery {
/**
* The index to use
*/
protected final AbstractRStarTree, ?> tree;
/**
* Spatial primitive distance function
*/
protected final SpatialPrimitiveDoubleDistanceFunction super O> distanceFunction;
/**
* Constructor.
*
* @param tree Index to use
* @param distanceQuery Distance query to use
* @param distanceFunction Distance function
*/
public DoubleDistanceRStarTreeKNNQuery(AbstractRStarTree, ?> tree, DistanceQuery distanceQuery, SpatialPrimitiveDoubleDistanceFunction super O> distanceFunction) {
super(distanceQuery);
this.tree = tree;
this.distanceFunction = distanceFunction;
}
/**
* Performs a k-nearest neighbor query for the given NumberVector with the
* given parameter k and the according distance function. The query result is
* in ascending order to the distance to the query object.
*
* @param object the query object
* @param knnList the knn list containing the result
*/
protected void doKNNQuery(O object, KNNHeap knnList) {
final Heap pq = new Heap(Math.min(knnList.getK() * 2, 20));
// push root
pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID()));
double maxDist = Double.MAX_VALUE;
// search in tree
while(!pq.isEmpty()) {
DoubleDistanceSearchCandidate pqNode = pq.poll();
if(pqNode.mindist > maxDist) {
return;
}
maxDist = expandNode(object, knnList, pq, maxDist, pqNode.nodeID);
}
}
private double expandNode(O object, KNNHeap knnList, final Heap 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++;
// 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()));
}
}
}
}
return maxDist;
}
/**
* Performs a batch knn query.
*
* @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> knnLists) {
if(node.isLeaf()) {
for(int i = 0; i < node.getNumEntries(); i++) {
SpatialEntry p = node.getEntry(i);
for(Entry> ent : knnLists.entrySet()) {
final DBID q = ent.getKey();
final KNNHeap knns_q = ent.getValue();
DoubleDistance knn_q_maxDist = knns_q.getKNNDistance();
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));
tree.distanceCalcs++;
if(dist_pq.compareTo(knn_q_maxDist) <= 0) {
knns_q.add(dist_pq, pid);
}
}
}
}
else {
ModifiableDBIDs ids = DBIDUtil.newArray(knnLists.size());
for(DBID id : knnLists.keySet()) {
ids.add(id);
}
List entries = getSortedEntries(node, ids);
for(DoubleDistanceEntry distEntry : entries) {
double minDist = distEntry.distance;
for(Entry> ent : knnLists.entrySet()) {
final KNNHeap knns_q = ent.getValue();
double knn_q_maxDist = knns_q.getKNNDistance().doubleValue();
if(minDist <= knn_q_maxDist) {
SpatialEntry entry = distEntry.entry;
AbstractRStarTreeNode, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID());
batchNN(child, knnLists);
break;
}
}
}
}
}
/**
* Sorts the entries of the specified node according to their minimum distance
* to the specified objects.
*
* @param node the node
* @param ids the id of the objects
* @return a list of the sorted entries
*/
protected List getSortedEntries(AbstractRStarTreeNode, ?> node, DBIDs ids) {
List result = new ArrayList();
for(int i = 0; i < node.getNumEntries(); i++) {
SpatialEntry entry = node.getEntry(i);
double minMinDist = Double.MAX_VALUE;
for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
double minDist = distanceFunction.doubleMinDist(entry, relation.get(iter));
tree.distanceCalcs++;
minMinDist = Math.min(minDist, minMinDist);
}
result.add(new DoubleDistanceEntry(entry, minMinDist));
}
Collections.sort(result);
return result;
}
/**
* Optimized double distance entry implementation.
*
* @author Erich Schubert
*
* @apiviz.hidden
*/
class DoubleDistanceEntry implements Comparable {
/**
* Referenced entry
*/
SpatialEntry entry;
/**
* Distance value
*/
double distance;
/**
* Constructor.
*
* @param entry Entry
* @param distance Distance
*/
public DoubleDistanceEntry(SpatialEntry entry, double distance) {
this.entry = entry;
this.distance = distance;
}
@Override
public int compareTo(DoubleDistanceEntry o) {
return Double.compare(this.distance, o.distance);
}
}
@Override
public KNNResult getKNNForObject(O obj, int k) {
if(k < 1) {
throw new IllegalArgumentException("At least one enumeration has to be requested!");
}
final KNNHeap knnList = new KNNHeap(k, distanceFunction.getDistanceFactory().infiniteDistance());
doKNNQuery(obj, knnList);
return knnList.toKNNList();
}
@Override
public KNNResult getKNNForDBID(DBIDRef id, int k) {
return getKNNForObject(relation.get(id), k);
}
@Override
public List> 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> knnLists = new HashMap>(ids.size());
for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
DBID id = iter.getDBID();
knnLists.put(id, new KNNHeap(k, distanceFunction.getDistanceFactory().infiniteDistance()));
}
batchNN(tree.getRoot(), knnLists);
List> result = new ArrayList>();
for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
DBID id = iter.getDBID();
result.add(knnLists.get(id).toKNNList());
}
return result;
}
@Override
public void getKNNForBulkHeaps(Map> heaps) {
AbstractRStarTreeNode, ?> root = tree.getRoot();
batchNN(root, heaps);
}
}