View Javadoc

1   package org.ajmm.obsearch.index;
2   
3   import java.io.File;
4   import java.io.IOException;
5   import java.util.BitSet;
6   import java.util.Iterator;
7   
8   import org.ajmm.obsearch.Index;
9   import org.ajmm.obsearch.Result;
10  import org.ajmm.obsearch.exception.IllegalIdException;
11  import org.ajmm.obsearch.exception.NotFrozenException;
12  import org.ajmm.obsearch.exception.OBException;
13  import org.ajmm.obsearch.exception.OutOfRangeException;
14  import org.ajmm.obsearch.index.utils.MyTupleInput;
15  import org.ajmm.obsearch.ob.OBShort;
16  import org.ajmm.obsearch.result.OBPriorityQueueShort;
17  import org.ajmm.obsearch.result.OBResultShort;
18  
19  import com.sleepycat.bind.tuple.IntegerBinding;
20  import com.sleepycat.bind.tuple.SortedFloatBinding;
21  import com.sleepycat.bind.tuple.TupleInput;
22  import com.sleepycat.bind.tuple.TupleOutput;
23  import com.sleepycat.je.Cursor;
24  import com.sleepycat.je.CursorConfig;
25  import com.sleepycat.je.DatabaseEntry;
26  import com.sleepycat.je.DatabaseException;
27  import com.sleepycat.je.LockMode;
28  import com.sleepycat.je.OperationStatus;
29  
30  /*
31   OBSearch: a distributed similarity search engine
32   This project is to similarity search what 'bit-torrent' is to downloads.
33   Copyright (C)  2007 Arnoldo Jose Muller Molina
34  
35   This program is free software: you can redistribute it and/or modify
36   it under the terms of the GNU General Public License as published by
37   the Free Software Foundation, either version 3 of the License, or
38   (at your option) any later version.
39  
40   This program is distributed in the hope that it will be useful,
41   but WITHOUT ANY WARRANTY; without even the implied warranty of
42   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
43   GNU General Public License for more details.
44  
45   You should have received a copy of the GNU General Public License
46   along with this program.  If not, see <http://www.gnu.org/licenses/>.
47   */
48  /**
49   * ExtendedPyramidIndexShort is an index that uses the pyramid technique. The
50   * distance function used must return short values. The spore file name is:
51   * ExtendedPyramidTechniqueShort
52   * @param <O>
53   *                The type of object to be stored in the Index.
54   * @author Arnoldo Jose Muller Molina
55   * @since 0.7
56   */
57  public class ExtendedPyramidIndexShort < O extends OBShort >
58          extends AbstractExtendedPyramidIndex < O > implements IndexShort < O > {
59  
60      /**
61       * Minimum value to be returned by the distance function.
62       */
63      private short minInput;
64  
65      /**
66       * Maximum value to be returned by the distance function.
67       */
68      private short maxInput;
69  
70      /**
71       * Creates a new ExtendedPyramidIndexShort. Ranges accepted by this pyramid
72       * will be between 0 and Short.MAX_VALUE
73       * @param databaseDirectory
74       *                Directory were the index will be stored
75       * @param pivots
76       *                Number of pivots to be used.
77       * @param pivotSelector
78       *                The pivot selector that will be used by this index.
79       * @param type The class of the object O that will be used.  
80       * @throws DatabaseException
81       *                 If something goes wrong with the DB
82       * @throws IOException
83       *                 If the databaseDirectory directory does not exist.
84       */
85      public ExtendedPyramidIndexShort(final File databaseDirectory,
86              final short pivots, PivotSelector < O > pivotSelector, Class<O> type)
87              throws DatabaseException, IOException {
88  
89          this(databaseDirectory, pivots, (short) 0, Short.MAX_VALUE,
90                  pivotSelector,type);
91      }
92  
93      /**
94       * Creates a new ExtendedPyramidIndexShort. Ranges accepted by this index
95       * will be defined by the user. We recommend the use of this constructor. We
96       * believe it will give better resolution to the float transformation. The
97       * values returned by the distance function must be within [minInput,
98       * maxInput]. These two values can be over estimated but not under
99       * estimated.
100      * @param databaseDirectory
101      *                Directory were the index will be stored
102      * @param pivots
103      *                Number of pivots to be used.
104      * @param minInput
105      *                Minimum value to be returned by the distance function
106      * @param maxInput
107      *                Maximum value to be returned by the distance function
108      * @param pivotSelector
109      *                The pivot selector that will be used by this index.
110      * @param type The class of the object O that will be used.  
111      * @throws DatabaseException
112      *                 If something goes wrong with the DB
113      * @throws IOException
114      *                 If the databaseDirectory directory does not exist.
115      */
116     public ExtendedPyramidIndexShort(final File databaseDirectory,
117             final short pivots, final short minInput, final short maxInput,
118             PivotSelector < O > pivotSelector,Class<O> type) throws DatabaseException,
119             IOException {
120         super(databaseDirectory, pivots, pivotSelector, type);
121         this.minInput = minInput;
122         this.maxInput = maxInput;
123         assert minInput < maxInput;
124     }
125 
126     @Override
127     protected float[] extractTuple(final TupleInput in)
128             throws OutOfRangeException {
129         int i = 0;
130         float[] res = new float[pivotsCount];
131         while (i < pivotsCount) {
132             res[i] = normalize(in.readShort());
133             i++;
134         }
135         return res;
136     }
137 
138     public boolean intersects(final O object, final short r, final int box)
139             throws NotFrozenException, DatabaseException,
140             InstantiationException, IllegalIdException, IllegalAccessException,
141             OutOfRangeException, OBException {
142         short[] t = new short[pivotsCount];
143         calculatePivotTuple(object, t); // calculate the pivot for the given
144         float[][] q = new float[pivotsCount][2]; // rectangular query
145         generateRectangle(t, r, q);
146         float[] lowHighResult = new float[2];
147         float[] minArray = generateMinArray(q);
148         return intersect(q, box, minArray, lowHighResult);
149     }
150 
151     public int[] intersectingBoxes(final O object, final short r)
152             throws NotFrozenException, DatabaseException,
153             InstantiationException, IllegalIdException, IllegalAccessException,
154             OutOfRangeException, OBException {
155         BitSet result = new BitSet(super.totalBoxes());
156         short[] t = new short[pivotsCount];
157         calculatePivotTuple(object, t); // calculate the pivot for the given
158         int pyramidCount = 2 * pivotsCount;
159         float[][] qorig = new float[pivotsCount][2]; // rectangular query
160         float[][] q = new float[pivotsCount][2]; // rectangular query
161         short myr = r;
162         float[] lowHighResult = new float[2];
163         generateRectangle(t, myr, qorig);
164         float[] minArray = generateMinArray(qorig);
165         int i = 0;
166         while (i < pyramidCount) {
167             copyQuery(qorig, q);
168             if (intersect(q, i, minArray, lowHighResult)) {
169                 result.set(i);
170             }
171             i++;
172         }
173         int[] res = new int[result.cardinality()];
174         i = 0;
175         int index = 0;
176         while (i < res.length) {
177             index = result.nextSetBit(index);
178             res[i] = index;
179             index++;
180             i++;
181         }
182         return res;
183     }
184 
185     public void searchOB(final O object, final short r,
186             final OBPriorityQueueShort < O > result) throws NotFrozenException,
187             DatabaseException, InstantiationException, IllegalIdException,
188             IllegalAccessException, OutOfRangeException, OBException {
189         // check if we are frozen
190         assertFrozen();
191 
192         short[] t = new short[pivotsCount];
193         calculatePivotTuple(object, t); // calculate the pivot for the given
194         // object
195 
196         int pyramidCount = 2 * pivotsCount;
197         float[][] qorig = new float[pivotsCount][2]; // rectangular query
198         float[][] q = new float[pivotsCount][2]; // rectangular query
199         short myr = r;
200         generateRectangle(t, myr, qorig);
201         int i = 0;
202         float[] lowHighResult = new float[2];
203         float[] minArray = generateMinArray(qorig);
204         while (i < pyramidCount) {
205             copyQuery(qorig, q);
206 
207             if (intersect(q, i, minArray, lowHighResult)) {
208                 searchBTreeAndUpdate(object, t, myr, i + lowHighResult[HLOW], i
209                         + lowHighResult[HHIGH], result);
210                 short nr = result.updateRange(myr);
211                 if (nr < myr) {
212                     myr = nr;
213                     // regenerate the query with a smaller range
214                     generateRectangle(t, myr, qorig);
215                 }
216             }
217             i++;
218         }
219     }
220 
221     public void searchOB(final O object, final short r,
222             final OBPriorityQueueShort < O > result, final int[] boxes)
223             throws NotFrozenException, DatabaseException,
224             InstantiationException, IllegalIdException, IllegalAccessException,
225             OutOfRangeException, OBException {
226         // check if we are frozen
227         assertFrozen();
228         BitSet boxesBit = new BitSet();
229         int i = 0;
230         while (i < boxes.length) {
231             boxesBit.set(boxes[i]);
232             i++;
233         }
234         short[] t = new short[pivotsCount];
235         calculatePivotTuple(object, t); // calculate the pivot for the given
236         // object
237 
238         int pyramidCount = 2 * pivotsCount;
239         float[][] qorig = new float[pivotsCount][2]; // rectangular query
240         float[][] q = new float[pivotsCount][2]; // rectangular query
241         short myr = r;
242         generateRectangle(t, myr, qorig);
243         i = 0;
244         float[] lowHighResult = new float[2];
245         // TODO: select the pyramids randomly just like quicksort
246         float[] minArray = generateMinArray(qorig);
247         while (i < pyramidCount) {
248             copyQuery(qorig, q);
249             if (intersect(q, i, minArray, lowHighResult) && boxesBit.get(i)) {
250                 searchBTreeAndUpdate(object, t, myr, i + lowHighResult[HLOW], i
251                         + lowHighResult[HHIGH], result);
252                 short nr = result.updateRange(myr);
253                 if (nr < myr) {
254                     myr = nr;
255                     // regenerate the query with a smaller range
256                     generateRectangle(t, myr, qorig);
257                 }
258             }
259             i++;
260         }
261     }
262 
263     /**
264      * This method reads from the B-tree appies l-infinite to discard false
265      * positives. This technique is called SMAP. Calculates the real distance
266      * and updates the result priority queue It is left public so that junit can
267      * perform validations on it Performance-wise this is one of the most
268      * important methods
269      * @param object
270      *                object to search
271      * @param tuple
272      *                tuple of the object
273      * @param r
274      *                range
275      * @param hlow
276      *                lowest pyramid value
277      * @param hhigh
278      *                highest pyramid value
279      * @param result
280      *                result of the search operation
281      * @throws DatabaseException
282      *                 If somehing goes wrong with the DB
283      * @throws OBException
284      *                 User generated exception
285      * @throws IllegalAccessException
286      *                 If there is a problem when instantiating objects O
287      * @throws InstantiationException
288      *                 If there is a problem when instantiating objects O
289      * @throws IllegalIdException
290      *                 This exception is left as a Debug flag. If you receive
291      *                 this exception please report the problem to:
292      *                 http://code.google.com/p/obsearch/issues/list
293      */
294     private void searchBTreeAndUpdate(final O object, final short[] tuple,
295             final short r, final float hlow, final float hhigh,
296             final OBPriorityQueueShort < O > result) throws DatabaseException,
297             IllegalAccessException, InstantiationException, IllegalIdException,
298             OBException {
299 
300         Cursor cursor = null;
301 
302         try {
303 
304             DatabaseEntry keyEntry = new DatabaseEntry();
305             DatabaseEntry dataEntry = new DatabaseEntry();
306             cursor = cDB.openCursor(null, null);
307             SortedFloatBinding.floatToEntry(hlow, keyEntry);
308             OperationStatus retVal = cursor.getSearchKeyRange(keyEntry,
309                     dataEntry, null);
310 
311             if (retVal == OperationStatus.NOTFOUND) {
312                 return;
313             }
314 
315             if (cursor.count() > 0) {
316                 float currentPyramidValue = SortedFloatBinding
317                         .entryToFloat(keyEntry);
318                 short max = Short.MIN_VALUE;
319                 short realDistance = Short.MIN_VALUE;
320                 while (retVal == OperationStatus.SUCCESS
321                         && currentPyramidValue <= hhigh) {
322 
323                     TupleInput in = new TupleInput(dataEntry.getData());
324 
325                     int i = 0;
326                     short t;
327                     max = Short.MIN_VALUE;
328                     while (i < tuple.length) {
329                         t = (short) Math.abs(tuple[i] - in.readShort());
330                         if (t > max) {
331                             max = t;
332                             if (t > r) {
333                                 break; // finish this loop this slice won't be
334                                 // matched
335                                 // after all!
336                             }
337                         }
338                         i++;
339                     }
340                     if (max <= r && result.isCandidate(max)) {
341                         // there is a chance it is a possible match
342                         int id = in.readInt();
343                         O toCompare = super.getObject(id);
344                         realDistance = object.distance(toCompare);
345                         if (realDistance <= r) {
346                             result.add(id, toCompare, realDistance);
347                         }
348                     }
349 
350                     // read the next record
351                     retVal = cursor.getNext(keyEntry, dataEntry, null);
352                     // update the current pyramid value so that we know when to
353                     // stop
354                     currentPyramidValue = SortedFloatBinding
355                             .entryToFloat(keyEntry);
356                 }
357             }
358         } finally {
359             cursor.close();
360         }
361     }
362 
363     /**
364      * Generates min and max for the given tuple It is actually the query. If
365      * you want non-rectangular queries you have to override this method and
366      * make sure your modification works well with searchOB
367      * @param t
368      *                the tuple to be processed
369      * @param r
370      *                the range
371      * @param q
372      *                resulting rectangle query
373      * @throws OutOfRangeException
374      *                 If the distance of any object to any other object exceeds
375      *                 the range defined by the user.
376      */
377 
378     protected final void generateRectangle(final short[] t, final short r,
379             final float[][] q) throws OutOfRangeException {
380         // range
381         int i = 0;
382         while (i < q.length) { //
383             q[i][MIN] = extendedPyramidNormalization(normalize((short) Math
384                     .max(t[i] - r, minInput)), i);
385             q[i][MAX] = extendedPyramidNormalization(normalize((short) Math
386                     .min(t[i] + r, maxInput)), i);
387             i++;
388         }
389         centerQuery(q);
390     }
391 
392     /**
393      * Method that takes the values already calculated in B and puts them into C
394      * This is to save some time when rebuilding the index.
395      * @throws DatabaseException
396      *                 If somehing goes wrong with the DB
397      * @throws OutOfRangeException
398      *                 If the distance of any object to any other object exceeds
399      *                 the range defined by the user.
400      */
401     @Override
402     protected void insertFromBtoC() throws DatabaseException,
403             OutOfRangeException {
404 
405         DatabaseEntry foundKey = new DatabaseEntry();
406         DatabaseEntry foundData = new DatabaseEntry();
407         Cursor cursor = null;
408         long count = super.bDB.count();
409         short[] t = new short[pivotsCount];
410         try {
411             int i = 0;
412             cursor = bDB.openCursor(null, null);
413             MyTupleInput in = new MyTupleInput();
414             while (cursor.getNext(foundKey, foundData, LockMode.DEFAULT) == OperationStatus.SUCCESS) {
415                 assert i == IntegerBinding.entryToInt(foundKey);
416                 // i contains the actual id of the tuple
417                 in.setBuffer(foundData.getData());
418                 int cx = 0;
419                 while (cx < t.length) {
420                     t[cx] = in.readShort();
421                     cx++;
422                 }
423                 this.insertFrozenAux(t, i);
424                 i++;
425             }
426             // Size reported by the DB and the items
427             // we read should be the same
428             assert i == count;
429 
430         } finally {
431             cursor.close();
432         }
433 
434     }
435 
436     /**
437      * Transforms the given tuple into an extended pyramid technique normalized
438      * value that considers the "center" of the dimension.
439      * @param tuple
440      *                The original tuple in the default dimension
441      * @throws OutOfRangeException
442      *                 If the distance of any object to any other object exceeds
443      *                 the range defined by the user.
444      * @return resulting normalized tuple
445      */
446     protected final float[] extendedPyramidTransform(final short[] tuple)
447             throws OutOfRangeException {
448         int i = 0;
449         float[] result = new float[tuple.length];
450         assert tuple.length == result.length;
451         while (i < tuple.length) {
452             float norm = normalize(tuple[i]);
453             float norm2 = extendedPyramidNormalization(norm, i);
454             result[i] = norm2;
455             i++;
456         }
457         return result;
458     }
459 
460     /**
461      * Normalize the given value.
462      * @param x
463      *                value to normalize
464      * @return the normalized value
465      * @throws OutOfRangeException
466      *                 If the distance of any object to any other object exceeds
467      *                 the range defined by the user.
468      */
469     protected float normalize(final short x) throws OutOfRangeException {
470         if (x < minInput || x > maxInput) {
471             throw new OutOfRangeException(minInput + "", maxInput + "", "" + x);
472         }
473         return ((float) (x - minInput)) / ((float) (maxInput - minInput));
474     }
475 
476     @Override
477     protected byte insertFrozen(final O object, final int id)
478             throws IllegalIdException, OBException, DatabaseException,
479             IllegalAccessException, InstantiationException {
480         short[] t = new short[pivotsCount];
481         calculatePivotTuple(object, t); // calculate the tuple for the new //
482 
483         return insertFrozenAux(t, id);
484     }
485 
486     public int getBox(final O object) throws OBException {
487         short[] t = new short[pivotsCount];
488         calculatePivotTuple(object, t); // calculate the tuple for the new //
489         float[] et = extendedPyramidTransform(t);
490         return super.pyramidOfPoint(et);
491     }
492 
493     public Result exists(O object) throws DatabaseException, OBException,
494             IllegalAccessException, InstantiationException {
495         Result res = new Result(Result.Status.NOT_EXISTS);
496 
497         short[] tuple = new short[pivotsCount];
498         // calculate the pivot for the given object
499         calculatePivotTuple(object, tuple);
500 
501         float[] et = extendedPyramidTransform(tuple);
502         float pyramidValue = pyramidValue(et);
503 
504         Cursor cursor = null;
505 
506         try {
507 
508             DatabaseEntry keyEntry = new DatabaseEntry();
509             DatabaseEntry dataEntry = new DatabaseEntry();
510             cursor = cDB.openCursor(null, null);
511             SortedFloatBinding.floatToEntry(pyramidValue, keyEntry);
512             OperationStatus retVal = cursor.getSearchKeyRange(keyEntry,
513                     dataEntry, null);
514 
515             if (retVal == OperationStatus.NOTFOUND) {
516                 return res;
517             }
518 
519             if (cursor.count() > 0) {
520                 float currentPyramidValue = SortedFloatBinding
521                         .entryToFloat(keyEntry);
522                 short max = Short.MIN_VALUE;
523                 while (retVal == OperationStatus.SUCCESS
524                         && currentPyramidValue == pyramidValue) {
525 
526                     TupleInput in = new TupleInput(dataEntry.getData());
527 
528                     int i = 0;
529                     short t;
530                     max = Short.MIN_VALUE;
531                     // STATS
532                     while (i < tuple.length) {
533                         t = (short) Math.abs(tuple[i] - in.readShort());
534                         if (t > max) {
535                             max = t;
536                             if (t != 0) {
537                                 break; // finish this loop this slice won't be
538                                 // matched
539                                 // after all!
540                             }
541                         }
542                         i++;
543                     }
544 
545                     // if max == 0 we can check the candidate
546 
547                     if (max == 0) {
548                         // there is a chance it is a possible match
549                         int id = in.readInt();
550                         O toCompare = super.getObject(id);
551                         if (object.equals(toCompare)) {
552                             res = new Result(Result.Status.EXISTS);
553                             res.setId(id);
554                             break;
555                         }
556 
557                     }
558                     // read the next record
559                     retVal = cursor.getNext(keyEntry, dataEntry, null);
560                     // update the current pyramid value so that we know when
561                     // to
562                     // stop
563                     currentPyramidValue = SortedFloatBinding
564                             .entryToFloat(keyEntry);
565                 }
566             }
567 
568         } finally {
569             if (cursor != null) {
570                 cursor.close();
571             }
572         }
573         return res;
574     }
575 
576     /**
577      * Inserts the given tuple and id into C
578      * @param t
579      *                tuple
580      * @param id
581      *                internal id
582      * @return 1 if everything was sucessful
583      * @throws OutOfRangeException
584      *                 If the distance of any object to any other object exceeds
585      *                 the range defined by the user.
586      * @throws DatabaseException
587      *                 If somehing goes wrong with the DB
588      */
589     protected byte insertFrozenAux(final short[] t, final int id)
590             throws OutOfRangeException, DatabaseException {
591         float[] et = extendedPyramidTransform(t);
592         float pyramidValue = pyramidValue(et);
593 
594         DatabaseEntry keyEntry = new DatabaseEntry();
595         DatabaseEntry dataEntry = new DatabaseEntry();
596         TupleOutput out = new TupleOutput();
597         // write the tuple
598         for (short d : t) {
599             out.writeShort(d);
600         }
601         // write the object's id
602         out.writeInt(id);
603         // create the key
604         SortedFloatBinding.floatToEntry(pyramidValue, keyEntry);
605         dataEntry.setData(out.getBufferBytes());
606 
607         if (cDB.put(null, keyEntry, dataEntry) != OperationStatus.SUCCESS) {
608             throw new DatabaseException();
609         }
610         return 1;
611     }
612 
613     @Override
614     protected void insertInB(final int id, final O object) throws OBException,
615             DatabaseException {
616         DatabaseEntry keyEntry = new DatabaseEntry();
617         TupleOutput out = new TupleOutput();
618         short[] tuple = new short[pivotsCount];
619         calculatePivotTuple(object, tuple);
620         // write the tuple
621         for (short d : tuple) {
622             out.writeShort(d);
623         }
624         // store the ID
625         IntegerBinding.intToEntry(id, keyEntry);
626         insertInDatabase(out, keyEntry, bDB);
627     }
628 
629     @Override
630     protected Index returnSelf() {
631         return this;
632     }
633 
634     /**
635      * Calculates the tuple vector for the given object.
636      * @param obj
637      *                object to be processed
638      * @param tuple
639      *                The resulting tuple will be stored here
640      * @throws OBException
641      *                 User generated exception
642      */
643     protected final void calculatePivotTuple(final O obj, final short[] tuple)
644             throws OBException {
645         assert tuple.length == pivotsCount;
646         int i = 0;
647         while (i < tuple.length) {
648             tuple[i] = obj.distance(pivots[i]);
649             i++;
650         }
651     }
652 
653     /*
654      * public Result exists(final O object) throws DatabaseException,
655      * OBException, IllegalAccessException, InstantiationException { Result res =
656      * new Result(Result.Status.NOT_EXISTS); OBPriorityQueueShort < O > result =
657      * new OBPriorityQueueShort < O >( (byte) 1); searchOB(object, (short) 1,
658      * result); if (result.getSize() == 1) { Iterator < OBResultShort < O >> it =
659      * result.iterator(); assert it.hasNext(); OBResultShort < O > r =
660      * it.next(); if (object.equals(r.getObject())) { res = new
661      * Result(Result.Status.EXISTS); res.setId(r.getId()); } } return res; }
662      */
663 
664     @Override
665     protected Result deleteAux(final O object) throws DatabaseException,
666             OBException, IllegalAccessException, InstantiationException {
667         int resId = -1;
668         Result res = new Result(Result.Status.NOT_EXISTS);
669         short[] tuple = new short[pivotsCount];
670         // calculate the pivot for the given object
671         calculatePivotTuple(object, tuple);
672         float[] et = extendedPyramidTransform(tuple);
673         float pyramidValue = pyramidValue(et);
674 
675         Cursor cursor = null;
676         try {
677 
678             CursorConfig config = new CursorConfig();
679             config.setReadUncommitted(true);
680             DatabaseEntry keyEntry = new DatabaseEntry();
681             DatabaseEntry dataEntry = new DatabaseEntry();
682             cursor = cDB.openCursor(null, null);
683             SortedFloatBinding.floatToEntry(pyramidValue, keyEntry);
684             OperationStatus retVal = cursor.getSearchKeyRange(keyEntry,
685                     dataEntry, null);
686 
687             if (retVal == OperationStatus.NOTFOUND) {
688                 // nothing to do here
689             } else if (cursor.count() > 0) {
690                 float currentPyramidValue = SortedFloatBinding
691                         .entryToFloat(keyEntry);
692                 short max = Short.MIN_VALUE;
693                 while (retVal == OperationStatus.SUCCESS
694                         && currentPyramidValue == pyramidValue) {
695 
696                     TupleInput in = new TupleInput(dataEntry.getData());
697 
698                     int i = 0;
699                     short t;
700                     max = Short.MIN_VALUE;
701                     // STATS
702                     while (i < tuple.length) {
703                         t = (short) Math.abs(tuple[i] - in.readShort());
704                         if (t > max) {
705                             max = t;
706                             if (t != 0) {
707                                 break; // finish this loop this slice won't be
708                                 // matched
709                                 // after all!
710                             }
711                         }
712                         i++;
713                     }
714 
715                     // if max == 0 we can check the candidate
716 
717                     if (max == 0) {
718                         // there is a chance it is a possible match
719                         int id = in.readInt();
720                         O toCompare = super.getObject(id);
721                         if (object.equals(toCompare)) {
722                             resId = id;
723                             res = new Result(Result.Status.OK);
724                             res.setId(resId);
725                             retVal = cursor.delete();
726                             // txn.commit();
727                             if (retVal != OperationStatus.SUCCESS) {
728                                 throw new DatabaseException();
729                             }
730                             break;
731                         }
732 
733                     }
734                     // read the next record
735                     retVal = cursor.getNext(keyEntry, dataEntry, null);
736                     // update the current pyramid value so that we know when
737                     // to
738                     // stop
739                     currentPyramidValue = SortedFloatBinding
740                             .entryToFloat(keyEntry);
741                 }
742 
743             }
744 
745         } finally {
746             if (cursor != null) {
747 
748                 cursor.close();
749             }
750         }
751         return res;
752     }
753 
754     public float distance(O a, O b) throws OBException {
755         short result = ((OBShort) a).distance((OBShort) b);
756         return normalize(result);
757     }
758 
759 }