1 package net.obsearch.result; 2 3 import net.obsearch.AbstractOBPriorityQueue; 4 import net.obsearch.ob.OBFloat; 5 import java.util.Iterator; 6 7 /* 8 OBSearch: a distributed similarity search engine 9 This project is to similarity search what 'bit-torrent' is to downloads. 10 Copyright (C) 2007 Arnoldo Jose Muller Molina 11 12 This program is free software: you can redistribute it and/or modify 13 it under the terms of the GNU General Public License as published by 14 the Free Software Foundation, either version 3 of the License, or 15 (at your option) any later version. 16 17 This program is distributed in the hope that it will be useful, 18 but WITHOUT ANY WARRANTY; without even the implied warranty of 19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 20 GNU General Public License for more details. 21 22 You should have received a copy of the GNU General Public License 23 along with this program. If not, see <http://www.gnu.org/licenses/>. 24 */ 25 /** 26 * This is a class used to efficiently perform k-nn searches. This queue is 27 * meant to be used with objects OBFloat. Inverted results will 28 * put first smaller values in the priority queue. 29 * @author Arnoldo Jose Muller Molina 30 * @since 0.7 31 */ 32 33 public final class OBPriorityQueueInvertedFloat<O> extends AbstractOBPriorityQueue<OBResultInvertedFloat<O>> { 34 35 /** 36 * Create the priority queue with k elements. This is how you set the k 37 * for a query. Use a negative value for a boundless queue. 38 */ 39 public OBPriorityQueueInvertedFloat(int k){ 40 super(k); 41 } 42 43 44 45 46 /** 47 * Add the given object, object id and distance of type float to the 48 * queue. This method tries to minimize the sizes of distances 49 * of the priority queue. 50 * @param id 51 * The id of the object to be used 52 * @param obj 53 * The object to be added 54 * @param distance 55 * The distance to be added 56 * @throws IllegalAccessException 57 * If there is a problem when instantiating objects O 58 * @throws InstantiationException 59 * If there is a problem when instantiating objects O 60 * @return true if the range has changed. 61 */ 62 public boolean add(long id, O obj, float distance) throws InstantiationException, IllegalAccessException { 63 if (queue.size() == k) { 64 // recycle objects. 65 66 if (queue.peek().getDistance() > distance) {// biggest object in 67 // the heap is 68 // bigger than d 69 OBResultInvertedFloat<O> c = queue.poll(); 70 c.setDistance(distance); 71 c.setObject(obj); 72 c.setId(id); 73 // assert validateAddition(c); 74 queue.offer(c); 75 return true; 76 } 77 78 } else { // if we are smaller than k we just create the object 79 OBResultInvertedFloat<O> c = new OBResultInvertedFloat<O>(); 80 c.setDistance(distance); 81 c.setObject(obj); 82 c.setId(id); 83 // assert validateAddition(c); 84 queue.offer(c); 85 } 86 return false; 87 //assert queue.size() <= k; 88 } 89 90 91 /** 92 * Add the given object, object id and distance of type float to the 93 * queue. This method tries to <b>maximize</b> the sizes of distances 94 * of the priority queue. 95 * @param id 96 * The id of the object to be used 97 * @param obj 98 * The object to be added 99 * @param distance 100 * The distance to be added 101 * @throws IllegalAccessException 102 * If there is a problem when instantiating objects O 103 * @throws InstantiationException 104 * If there is a problem when instantiating objects O 105 */ 106 public void addMax(long id, O obj, float distance) throws InstantiationException, IllegalAccessException { 107 if (queue.size() == k) { 108 // recycle objects. 109 110 if (queue.peek().getDistance() < distance) {// biggest object in 111 // the heap is 112 // bigger than d 113 OBResultInvertedFloat<O> c = queue.poll(); 114 c.setDistance(distance); 115 c.setObject(obj); 116 c.setId(id); 117 // assert validateAddition(c); 118 queue.offer(c); 119 } 120 } else { // if we are smaller than k we just create the object 121 OBResultInvertedFloat<O> c = new OBResultInvertedFloat<O>(); 122 c.setDistance(distance); 123 c.setObject(obj); 124 c.setId(id); 125 // assert validateAddition(c); 126 queue.offer(c); 127 } 128 //assert queue.size() <= k; 129 } 130 131 /** 132 * Make sure no repeated elements are added 133 */ 134 private boolean validateAddition(OBResultInvertedFloat<O> c){ 135 Iterator<OBResultInvertedFloat<O>> it = iterator(); 136 while(it.hasNext()){ 137 OBResultInvertedFloat<O> t = it.next(); 138 if(t.getId() == c.getId()){ 139 return false; 140 } 141 } 142 return false; 143 } 144 145 /** 146 * If queue.size() == k, then if the user's range is greater than the 147 * greatest element of the queue, we can reduce the range to the biggest 148 * element of the priority queue, that is its queue.peek() element. 149 * @param r 150 * The new range we want to calculate. 151 * @return the new range or the old range if the above condition is not 152 * met 153 */ 154 public float updateRange(float r) { 155 // TODO: update the pyramid technique range so that we reduce the 156 // searches in the 157 // remaining pyramids. We could start actually matching random pyramids 158 // and then hope we can get a very small r at the beginning 159 // if so, the other pyramids will be cheaper to search. 160 // in paralell mode we could take the first 2 * d queries and then match 161 // one pyramid by one each of the queries waiting to get the sub result, 162 // update the range 163 // and then continue... this can potentially improve performance. 164 if (this.getSize() == k) { 165 float d = queue.peek().getDistance(); 166 if (d < r) { 167 return d; // return d 168 } 169 } 170 return r; // return d if we cannot safely reduce the range 171 } 172 173 /** 174 * Returns true if the given distance can be a candidate for adding it into 175 * the queue. The parameter d is an estimation of the real distance, and 176 * this method is used to decide if we should calculate the real distance. 177 * @param d 178 * The lower resolution distance. 179 * @return True if we should calculate the real distance and attempt add the 180 * corresponding object into this queue. 181 */ 182 public boolean isCandidate(float d){ 183 if(this.getSize() == k ){ 184 // d should be less than the biggest candiate 185 // to be considered 186 return d < queue.peek().getDistance(); 187 } 188 // if the queue is smaller than k, 189 // everybody is a candidate 190 return true; 191 } 192 193 194 195 } 196 197