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
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 public final class OBQueryFloat<O extends OBFloat> extends AbstractOBQuery<O> {
38
39
40 private OBResultFloat<O> query;
41
42
43
44 protected OBPriorityQueueFloat<O> result;
45
46
47
48
49 protected float[] min;
50
51
52
53
54
55 protected float[] max;
56
57
58
59
60
61
62 protected float[] smap;
63
64
65
66
67 public OBQueryFloat(){
68 }
69
70 public O getObject(){
71 return query.getObject();
72 }
73
74
75
76
77
78
79
80
81
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
97
98
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
118
119
120
121
122
123
124
125
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
152
153 public float[] getLow(){
154 return min;
155 }
156
157
158
159
160 public float[] getHigh(){
161 return max;
162 }
163
164
165
166
167 public OBPriorityQueueFloat<O> getResult(){
168 return result;
169 }
170
171
172
173
174
175
176 public void setResult(OBPriorityQueueFloat<O> result){
177 this.result = result;
178 }
179
180
181
182
183
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
209
210
211
212
213
214
215
216
217
218
219
220
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
240 return (float)Math.min(query.getDistance(), result.peek().getDistance());
241 }else{
242 return query.getDistance();
243 }
244 }
245
246
247
248
249
250 public boolean updatedRange(float originalRange){
251 return query.getDistance() != originalRange;
252 }
253
254
255
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
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
310
311 public double ep(float[] dbin){
312 return epAux(dbin) * (1 / (double)getResult().getSize());
313 }
314
315
316
317
318
319
320
321
322
323 public double approx(float[] dbin) throws OBException {
324
325 List<OBResultFloat<O>> query = getResult().getSortedElements();
326
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
337
338
339 private double epAux(float[] dbin){
340 List<OBResultFloat<O>> query = getResult().getSortedElements();
341 int i = 0;
342 int result = 0;
343
344 Set<Integer> s = new HashSet<Integer>();
345 for(OBResultFloat<O> r : query){
346
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
369
370 public double compound(float[] dbin){
371 List<OBResultFloat<O>> query = getResult().getSortedElements();
372 int i = 0;
373
374 double res = 0;
375
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
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
394
395 public double rde(float[] dbin){
396 return rdeAux(dbin) / (double) getResult().getSize();
397 }
398
399
400
401
402 private double rdeAux(float[] dbin){
403 List<OBResultFloat<O>> query = getResult().getSortedElements();
404 int i = 0;
405 double result = 0;
406
407 for(OBResultFloat<O> r : query){
408
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
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
427 for(OBResultFloat<O> r : query){
428
429 up += (double)dbin[i];
430 down += (double) r.getDistance();
431 i++;
432 }
433 return up / down;
434 }
435
436
437
438
439 public double precision(float[] dbin){
440 List<OBResultFloat<O>> query = getResult().getSortedElements();
441 int count = 0;
442
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
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
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