1 /* 2 * This file is part of ELKI: 3 * Environment for Developing KDD-Applications Supported by Index-Structures 4 * 5 * Copyright (C) 2018 6 * ELKI Development Team 7 * 8 * This program is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Affero General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Affero General Public License for more details. 17 * 18 * You should have received a copy of the GNU Affero General Public License 19 * along with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; 22 23 import de.lmu.ifi.dbs.elki.database.ids.DBID; 24 import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; 25 import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; 26 import de.lmu.ifi.dbs.elki.database.ids.KNNList; 27 import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; 28 import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; 29 import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; 30 import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; 31 import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; 32 import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; 33 import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; 34 35 /** 36 * Instance of a KNN query for a particular spatial index. 37 * 38 * @author Erich Schubert 39 * @since 0.4.0 40 * 41 * @assoc - - - AbstractMTree 42 * @assoc - - - MTreeSearchCandidate 43 * 44 * @param <O> Object type 45 */ 46 public class MTreeKNNQuery<O> extends AbstractDistanceKNNQuery<O> { 47 /** 48 * The index to use 49 */ 50 protected final AbstractMTree<O, ?, ?, ?> index; 51 52 /** 53 * Constructor. 54 * 55 * @param index Index to use 56 * @param distanceQuery Distance query used 57 */ MTreeKNNQuery(AbstractMTree<O, ?, ?, ?> index, DistanceQuery<O> distanceQuery)58 public MTreeKNNQuery(AbstractMTree<O, ?, ?, ?> index, DistanceQuery<O> distanceQuery) { 59 super(distanceQuery); 60 this.index = index; 61 } 62 63 @Override getKNNForObject(O q, int k)64 public KNNList getKNNForObject(O q, int k) { 65 if(k < 1) { 66 throw new IllegalArgumentException("At least one object has to be requested!"); 67 } 68 index.statistics.countKNNQuery(); 69 70 KNNHeap knnList = DBIDUtil.newHeap(k); 71 double d_k = Double.POSITIVE_INFINITY; 72 73 final ComparableMinHeap<MTreeSearchCandidate> pq = new ComparableMinHeap<>(); 74 75 // Push the root node 76 pq.add(new MTreeSearchCandidate(0., index.getRootID(), null, 0.)); 77 78 // search in tree 79 while(!pq.isEmpty()) { 80 MTreeSearchCandidate pqNode = pq.poll(); 81 82 if(knnList.size() >= k && pqNode.mindist > d_k) { 83 break; 84 } 85 86 AbstractMTreeNode<?, ?, ?> node = index.getNode(pqNode.nodeID); 87 DBID id_p = pqNode.routingObjectID; 88 double d1 = pqNode.routingDistance; 89 90 // directory node 91 if(!node.isLeaf()) { 92 for(int i = 0; i < node.getNumEntries(); i++) { 93 MTreeEntry entry = node.getEntry(i); 94 DBID o_r = entry.getRoutingObjectID(); 95 double r_or = entry.getCoveringRadius(); 96 double d2 = id_p != null ? entry.getParentDistance() : 0.; 97 98 double diff = Math.abs(d1 - d2); 99 100 double sum = d_k + r_or; 101 102 if(diff <= sum) { 103 double d3 = distanceQuery.distance(o_r, q); 104 index.statistics.countDistanceCalculation(); 105 double d_min = Math.max(d3 - r_or, 0.); 106 if(d_min <= d_k) { 107 pq.add(new MTreeSearchCandidate(d_min, ((DirectoryEntry) entry).getPageID(), o_r, d3)); 108 } 109 } 110 } 111 } 112 // data node 113 else { 114 for(int i = 0; i < node.getNumEntries(); i++) { 115 MTreeEntry entry = node.getEntry(i); 116 DBID o_j = entry.getRoutingObjectID(); 117 118 double d2 = id_p != null ? entry.getParentDistance() : 0.; 119 120 double diff = Math.abs(d1 - d2); 121 122 if(diff <= d_k) { 123 double d3 = distanceQuery.distance(o_j, q); 124 index.statistics.countDistanceCalculation(); 125 if(d3 <= d_k) { 126 knnList.insert(d3, o_j); 127 d_k = knnList.getKNNDistance(); 128 } 129 } 130 } 131 } 132 } 133 return knnList.toKNNList(); 134 } 135 } 136