View Javadoc

1   package net.obsearch.query;
2   import java.util.List;
3   import java.util.LinkedList;
4   import java.util.HashSet;
5   import java.util.Set;
6   import net.obsearch.ob.OBFloat;
7   import net.obsearch.result.OBResultFloat;
8   import net.obsearch.result.OBPriorityQueueFloat;
9   import net.obsearch.exception.OBException;
10  import net.obsearch.AbstractOBResult;
11  import net.obsearch.asserts.OBAsserts;
12  /*
13      OBSearch: a distributed similarity search engine
14      This project is to similarity search what 'bit-torrent' is to downloads.
15      Copyright (C)  2007 Arnoldo Jose Muller Molina
16  
17    	This program is free software: you can redistribute it and/or modify
18      it under the terms of the GNU General Public License as published by
19      the Free Software Foundation, either version 3 of the License, or
20      (at your option) any later version.
21  
22      This program is distributed in the hope that it will be useful,
23      but WITHOUT ANY WARRANTY; without even the implied warranty of
24      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25      GNU General Public License for more details.
26  
27      You should have received a copy of the GNU General Public License
28      along with this program.  If not, see <http://www.gnu.org/licenses/>.
29   */
30  /**
31   * Object used to store a query request.
32   * @author Arnoldo Jose Muller Molina
33   * @since 0.7
34   */
35  
36  
37  public final class OBQueryFloat<O extends OBFloat> extends AbstractOBQuery<O> {
38  
39  
40  		private OBResultFloat<O> query;
41      /**
42       * Holds the results for the query.
43       */
44      protected OBPriorityQueueFloat<O> result;
45  
46      /**
47       * Minimum part of the rectangle of the query.
48       */ 
49  		protected float[] min;
50  
51  		
52  		/**
53       * Maximum part of the rectangle of the query.
54       */ 
55  		protected float[] max;
56  
57  		
58  		/**
59       * SMAPed vector
60       */ 
61  
62  		protected float[] smap;
63  
64      /**
65       * Constructor.
66       */
67      public OBQueryFloat(){
68      }
69  
70  		public O getObject(){
71  				return query.getObject();
72  		}
73  
74      /**
75       * Creates a new OBQueryFloat object.
76       * @param object
77       *            The object that will be matched.
78       * @param range
79       *            The range to be used for the match.
80       * @param result
81       *            The priority queue were the results will be stored.
82       */
83      public OBQueryFloat(O object, float range, OBPriorityQueueFloat<O> result){
84  
85          query = new OBResultFloat<O>(object,-1,range);
86          this.result = result;
87      }
88  
89  		public OBQueryFloat(O object, OBPriorityQueueFloat<O> result){
90  				this(object, Float.MAX_VALUE, result);
91  		}
92  
93  		
94  
95  		/**
96  		 * Returns true if the given rectangle collides
97       * with this query.
98       * @param rectangle The rectangle to search.
99       */
100 		public boolean collides(float[][] rectangle){
101 				float[] minOther = rectangle[0];
102 				float[] maxOther = rectangle[1];
103 				boolean res = true;
104 				assert minOther.length == smap.length;
105 				int i = 0;
106 				while (i < minOther.length) {
107 				    if(max[i] < minOther[i] || min[i] > maxOther[i]){
108 								res =false;
109 								break;
110 						}
111 				    i++;
112 				}
113 				return res;
114 		}
115 
116 		/**
117      * Creates a new OBQueryFloat object.
118      * @param object
119      *            The object that will be matched.
120      * @param range
121      *            The range to be used for the match.
122      * @param result
123      *            The priority queue were the results will be stored.
124 		 * @param smap 
125      *            SMAP vector representation of the given object.
126      */
127     public OBQueryFloat(O object, float range, OBPriorityQueueFloat<O> result, float[] smap){
128 
129         this(object,range,result);
130 				this.smap = smap;
131 				if(smap != null){
132 						min = new float[smap.length];
133 				max = new float[smap.length];
134 				}
135 				updateRectangle();
136 				
137     }
138 
139 		private void updateRectangle(){
140 				if(smap != null){
141 				int i = 0;
142 				while (i < smap.length) {
143 				    min[i] = (float)Math.max(smap[i] - query.getDistance(), 0);
144 						max[i] = (float)Math.min(smap[i] + query.getDistance(), Float.MAX_VALUE);
145 				    i++;
146 				}
147 				}
148 		}
149 
150 		/**
151 		 * Return low of the query rectangle.
152      */ 
153 		public float[] getLow(){
154 				return min;
155 		}
156 
157 		/**
158 		 * Return low of the query rectangle.
159      */ 
160 		public float[] getHigh(){
161 				return max;
162 		}
163 
164     /**
165      * @return The current results of the matching.
166      */
167     public OBPriorityQueueFloat<O> getResult(){
168         return result;
169     }
170 
171     /**
172      * Set the results of the matching to a new object.
173      * @param result
174      *            The new result.
175      */
176     public void setResult(OBPriorityQueueFloat<O> result){
177         this.result = result;
178     }
179 
180    /**
181     * Returns true if we should calculate the real distance.
182     * @param smapDistance The lower-resolution distance calculated
183     * with SMAP.
184     * 
185     */
186     public boolean isCandidate(float smapDistance){
187         return smapDistance <= query.getDistance() && result.isCandidate(smapDistance);
188     }
189 
190 
191 		public  boolean add(long id, O object) throws InstantiationException, IllegalAccessException , OBException{
192 				return add(id, object,  query.getObject().distance(object));
193 		}
194 
195 		public float getDistance(){
196 				return query.getDistance();
197 		}
198 
199 		public List<AbstractOBResult<O>> getSortedElements(){
200 				List<AbstractOBResult<O>> res = new LinkedList<AbstractOBResult<O>>();
201 				for(OBResultFloat<O> r : result.getSortedElements()){
202 						res.add(r);
203 				}
204 				return res;	
205 		}
206 
207    /**
208     * Add the given object, object id and distance of type float to the
209     * queue. Updates the range of the query as needed if the range
210     * shrinks after this insertion.
211     * @param id
212     *            The id of the object to be used
213     * @param obj
214     *            The object to be added
215     * @param d
216     *            The distance to be added
217     * @throws IllegalAccessException
218     *             If there is a problem when instantiating objects O
219     * @throws InstantiationException
220     *             If there is a problem when instantiating objects O
221     */
222     public boolean add(long id, O obj, float d) throws InstantiationException, IllegalAccessException {
223 				if(d <= currentRange()){
224 				boolean res = result.add(id,obj,d);
225 				float temp = result.updateRange(query.getDistance());
226 				if(temp != query.getDistance()){
227 								 query.setDistance( temp );
228 
229 						updateRectangle();
230         }
231 				return res;
232 				}else{
233 						return false;
234 				}
235 		}
236 
237 		private float currentRange(){
238 				if(result.getSize() == result.getK()){
239 						//						assert result.peek().getDistance() <= query.getDistance();
240 						return (float)Math.min(query.getDistance(), result.peek().getDistance());
241 				}else{
242 						return query.getDistance();
243 				}
244 		}
245 
246 		/**
247 		 * Returns true if the originalRange has been modified.
248 		 * @return true If the current range (getDistance()) is different than originalRange.
249 		 */
250 		public boolean updatedRange(float originalRange){
251 				return query.getDistance() != originalRange;
252 		}
253 
254 		/**
255 		 * @return true if the underlying priority queue's size is equal to k
256      */
257 		public boolean isFull(){
258 				return result.isFull();
259 		}
260 
261 
262 		public  double recall(List<AbstractOBResult<O>> perfectQuery){
263 				int hits = 0;
264 				Set<AbstractOBResult<O>> s = new HashSet<AbstractOBResult<O>>();
265 				for(OBResultFloat<O> r : this.result.getSortedElements()){			
266 						int i = 0;
267 						for(AbstractOBResult<O> d : perfectQuery){
268 								if(! s.contains(d) && d.compareTo(r) == 0){
269 										s.add(d);
270 										hits++;
271 										break;
272 								}
273 								i++;
274 						}
275 				}
276 				return (double)hits / (double)perfectQuery.size();
277 		}
278 
279 
280 		public  double ep(List<AbstractOBResult<O>> dbin){
281 				List<OBResultFloat<O>> query = getResult().getSortedElements();
282 				int i = 0;
283 				int result = 0;
284 				Set<OBResultFloat<O>> s = new HashSet<OBResultFloat<O>>();
285 				for(OBResultFloat<O> r : query){
286 						// find the position in the db. 
287 						int cx = 0;
288 						for(AbstractOBResult<O> cr : dbin){
289 								OBResultFloat<O> c = (OBResultFloat<O>)cr;
290 								if(! s.contains(c) &&c.compareTo(r) == 0){
291 										s.add(c);
292 										result += cx - i;
293 										break;
294 								}
295 								cx++;
296 						}
297 						i++;
298 				}
299 				if(query.size() == 0){
300 						return 0;
301 				}else{
302 						double res = ((double)result)/ ((double)(query.size() * dbin.size()));
303 						return res;
304 				}
305 		}
306 
307 
308 		/**
309      * Calculate the EP value for a sorted list of distances.
310      */
311 		public  double ep(float[] dbin){
312 				return epAux(dbin) * (1 / (double)getResult().getSize());
313 		}
314 
315 		
316 				/**
317 	 * Calculate the 1 + E  or (c for Adonis et al) for approx. nearest neighbor
318 	 * This is the approximation and "real" is the real result.
319 	 * @param q
320 	 * @return
321 	 * @throws RAException
322 	 */
323 		public double approx(float[] dbin) throws OBException {
324 
325 				List<OBResultFloat<O>> query = getResult().getSortedElements();
326 		// get the last guys
327 		if(! this.isFull()){
328 				return 1;
329 		}
330 		
331 		int last = query.size() - 1;
332 		return Math.abs((query.get(last).getDistance()) / dbin[last]);
333 	}
334 
335 		/**
336      * Calculate the EP value for a sorted list of distances.
337 		 * Does not multiply by 1/k
338      */
339 		private  double epAux(float[] dbin){
340 				List<OBResultFloat<O>> query = getResult().getSortedElements();
341 				int i = 0;
342 				int result = 0;
343         // hold the visited elements
344 				Set<Integer> s = new HashSet<Integer>();
345 				for(OBResultFloat<O> r : query){
346 						// find the position in the db. 
347 						int cx = 0;
348 						for(float cr : dbin){								
349 								if(! s.contains(cx) && cr == r.getDistance()){
350 										s.add(cx);
351 										result += cx - i;
352 										break;
353 								}
354 								cx++;
355 						}
356 						i++;
357 				}
358 				if(query.size() == 0){
359 						return 0;
360 				}else{
361 						double res = ((double)result)/ ((double)(dbin.length));
362 						return res;
363 				}
364 		}
365 
366 
367 		/**
368 		 * Calculates ep without multiplying by 1/k and 
369 		 */ 
370 		public  double compound(float[] dbin){
371 				List<OBResultFloat<O>> query = getResult().getSortedElements();
372 				int i = 0;
373 				
374 				double res = 0;
375         // hold the visited elements
376 				Set<Integer> s = new HashSet<Integer>();
377 				for(OBResultFloat<O> r : query){
378 
379 						double ep = 1 - (((double)rank(r.getDistance(), dbin) - (i))/(double)(dbin.length));
380 						// fix rounding error
381 						if(r.getDistance() == 0){
382 								assert dbin[i] == 0;
383 								res += 1;
384 						}else{
385 								res += ((double)dbin[i] / (double)r.getDistance()) * ep;
386 						}
387 						i++;
388 				}
389 				return res / (double) query.size();
390 		}
391 
392 		/*
393 		 * Calculates the relative distance error.
394 		 */
395     public double rde(float[] dbin){
396 				return rdeAux(dbin) / (double) getResult().getSize();
397 		}
398 
399 		/*
400 		 * Calculates the relative distance error without dividing by 1/k
401 		 */
402 		private  double rdeAux(float[] dbin){
403 				List<OBResultFloat<O>> query = getResult().getSortedElements();
404 				int i = 0;
405 				double result = 0;
406         // hold the visited elements
407 				for(OBResultFloat<O> r : query){
408 						// find the position in the db. 
409 						if(dbin[i] != 0){
410 								result +=  ( (double) r.getDistance() / (double)dbin[i]) - 1; 
411 						}
412 						i++;
413 				}
414 				return result;
415 		}
416 
417 
418 		/**
419 		 * Total distance ratio
420 		 */
421 		public  double tDR(float[] dbin){
422 				List<OBResultFloat<O>> query = getResult().getSortedElements();
423 				int i = 0;
424 				double up = 0;
425 				double down = 0;
426         // hold the visited elements
427 				for(OBResultFloat<O> r : query){
428 						// find the position in the db. 
429 						up += (double)dbin[i];
430 						down += (double) r.getDistance();
431 						i++;
432 				}
433 				return up / down;
434 		}
435 
436 		/** 
437      * Calculates the precision
438 		 */
439 		public double precision(float[] dbin){
440 				List<OBResultFloat<O>> query = getResult().getSortedElements();
441 				int count = 0;
442         // hold the visited elements
443 				for(OBResultFloat<O> r : query){
444 						if(rank(r.getDistance(), dbin) < query.size()) {
445 								count++;
446 						}
447 				}
448 				return (double) count / (double) query.size();
449 		}
450 
451 		/**
452 		 * find the position of distance in the given dbin list
453 		 */ 
454 		private int rank(float distance, float[] dbin){
455 				int i = 0;
456 				while(i < dbin.length){
457 						if(distance == dbin[i]){
458 								break;
459 						}
460 						i++;
461 				}
462 				return i;
463 		}
464 
465 		/**
466 		 * peek to the largest value if the queue is full.
467 		 */
468 		public float peek() throws OBException{
469 				OBAsserts.chkAssert(isFull(), "Queue is not full");
470 				return result.peek().getDistance();
471 		}
472 		
473 }
474 
475