View Javadoc

1   package net.obsearch.result;
2   
3   import net.obsearch.AbstractOBPriorityQueue;
4   import net.obsearch.ob.OBLong;
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 OBLong. 
28   * @author Arnoldo Jose Muller Molina
29   * @since 0.7
30   */
31  
32  public final class OBPriorityQueueLong<O> extends AbstractOBPriorityQueue<OBResultLong<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 OBPriorityQueueLong(int k){
39          super(k);
40      }
41  
42  		
43  		
44  		
45      /**
46       * Add the given object, object id and distance of type long 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, long 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                  OBResultLong<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              OBResultLong<O> c = new OBResultLong<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 long 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, long 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                 OBResultLong<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             OBResultLong<O> c = new OBResultLong<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(OBResultLong<O> c){
134 				Iterator<OBResultLong<O>> it = iterator();
135 				while(it.hasNext()){
136 						OBResultLong<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 long updateRange(long 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             long 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(long 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