View Javadoc

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