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. 28 * @author Arnoldo Jose Muller Molina 29 * @since 0.7 30 */ 31 32 public final class OBPriorityQueueFloat<O> extends AbstractOBPriorityQueue<OBResultFloat<O>> { 33 34 /** 35 * Create the priority queue with k elements. This is how you set the k 36 * for a query. Use a negative value for a boundless queue. 37 */ 38 public OBPriorityQueueFloat(int k){ 39 super(k); 40 } 41 42 43 44 45 /** 46 * Add the given object, object id and distance of type float to the 47 * queue. This method tries to minimize the sizes of distances 48 * of the priority queue. 49 * @param id 50 * The id of the object to be used 51 * @param obj 52 * The object to be added 53 * @param distance 54 * The distance to be added 55 * @throws IllegalAccessException 56 * If there is a problem when instantiating objects O 57 * @throws InstantiationException 58 * If there is a problem when instantiating objects O 59 * @return true if the range has changed. 60 */ 61 public boolean add(long id, O obj, float distance) throws InstantiationException, IllegalAccessException { 62 if (queue.size() == k) { 63 // recycle objects. 64 65 if (queue.peek().getDistance() > distance) {// biggest object in 66 // the heap is 67 // bigger than d 68 OBResultFloat<O> c = queue.poll(); 69 c.setDistance(distance); 70 c.setObject(obj); 71 c.setId(id); 72 // assert validateAddition(c); 73 queue.offer(c); 74 return true; 75 } 76 77 } else { // if we are smaller than k we just create the object 78 OBResultFloat<O> c = new OBResultFloat<O>(); 79 c.setDistance(distance); 80 c.setObject(obj); 81 c.setId(id); 82 // assert validateAddition(c); 83 queue.offer(c); 84 } 85 return false; 86 //assert queue.size() <= k; 87 } 88 89 90 /** 91 * Add the given object, object id and distance of type float to the 92 * queue. This method tries to <b>maximize</b> the sizes of distances 93 * of the priority queue. 94 * @param id 95 * The id of the object to be used 96 * @param obj 97 * The object to be added 98 * @param distance 99 * The distance to be added 100 * @throws IllegalAccessException 101 * If there is a problem when instantiating objects O 102 * @throws InstantiationException 103 * If there is a problem when instantiating objects O 104 */ 105 public void addMax(long id, O obj, float distance) throws InstantiationException, IllegalAccessException { 106 if (queue.size() == k) { 107 // recycle objects. 108 109 if (queue.peek().getDistance() < distance) {// biggest object in 110 // the heap is 111 // bigger than d 112 OBResultFloat<O> c = queue.poll(); 113 c.setDistance(distance); 114 c.setObject(obj); 115 c.setId(id); 116 // assert validateAddition(c); 117 queue.offer(c); 118 } 119 } else { // if we are smaller than k we just create the object 120 OBResultFloat<O> c = new OBResultFloat<O>(); 121 c.setDistance(distance); 122 c.setObject(obj); 123 c.setId(id); 124 // assert validateAddition(c); 125 queue.offer(c); 126 } 127 //assert queue.size() <= k; 128 } 129 130 /** 131 * Make sure no repeated elements are added 132 */ 133 private boolean validateAddition(OBResultFloat<O> c){ 134 Iterator<OBResultFloat<O>> it = iterator(); 135 while(it.hasNext()){ 136 OBResultFloat<O> t = it.next(); 137 if(t.getId() == c.getId()){ 138 return false; 139 } 140 } 141 return false; 142 } 143 144 /** 145 * If queue.size() == k, then if the user's range is greater than the 146 * greatest element of the queue, we can reduce the range to the biggest 147 * element of the priority queue, that is its queue.peek() element. 148 * @param r 149 * The new range we want to calculate. 150 * @return the new range or the old range if the above condition is not 151 * met 152 */ 153 public float updateRange(float r) { 154 // TODO: update the pyramid technique range so that we reduce the 155 // searches in the 156 // remaining pyramids. We could start actually matching random pyramids 157 // and then hope we can get a very small r at the beginning 158 // if so, the other pyramids will be cheaper to search. 159 // in paralell mode we could take the first 2 * d queries and then match 160 // one pyramid by one each of the queries waiting to get the sub result, 161 // update the range 162 // and then continue... this can potentially improve performance. 163 if (this.getSize() == k) { 164 float d = queue.peek().getDistance(); 165 if (d < r) { 166 return d; // return d 167 } 168 } 169 return r; // return d if we cannot safely reduce the range 170 } 171 172 /** 173 * Returns true if the given distance can be a candidate for adding it into 174 * the queue. The parameter d is an estimation of the real distance, and 175 * this method is used to decide if we should calculate the real distance. 176 * @param d 177 * The lower resolution distance. 178 * @return True if we should calculate the real distance and attempt add the 179 * corresponding object into this queue. 180 */ 181 public boolean isCandidate(float d){ 182 if(this.getSize() == k ){ 183 // d should be less than the biggest candiate 184 // to be considered 185 return d < queue.peek().getDistance(); 186 } 187 // if the queue is smaller than k, 188 // everybody is a candidate 189 return true; 190 } 191 192 193 194 } 195 196