1 package org.ajmm.obsearch.index.pptree;
2
3 import java.util.Arrays;
4 import java.util.List;
5
6 /*
7 OBSearch: a distributed similarity search engine
8 This project is to similarity search what 'bit-torrent' is to downloads.
9 Copyright (C) 2007 Arnoldo Jose Muller Molina
10
11 This program is free software: you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation, either version 3 of the License, or
14 (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program. If not, see <http://www.gnu.org/licenses/>.
23 */
24 /**
25 * A SpaceTreeLeaf stores the minimum and maximum values of a hyperrectangle.
26 * All the space is divided in subspaces and a SpaceTreeLeaf is one of them. The
27 * {@link #SNo} property holds the identification number of the subspace. A
28 * SpaceTreeLeaf can normalize a value and a query in terms of the subspace.
29 * Inside this subspace we apply the extended pyramid technique.
30 * @author Arnoldo Jose Muller Molina
31 * @since 0.7
32 */
33
34 public class SpaceTreeLeaf extends AbstractSpaceTreeNode implements SpaceTree {
35
36
37
38 /**
39 * Space number.
40 */
41 private int SNo;
42
43 /**
44 * Minimum value for the dimension.
45 */
46 private double[] min;
47
48 /**
49 * Width of the dimension.
50 */
51 private double[] width;
52
53 /**
54 * Pre-calculated value for normalization.
55 */
56 private double[] exp;
57
58 /**
59 * Initializes the leaf with the given cluster center.
60 * @param center The center of this space.
61 */
62 public SpaceTreeLeaf(float[] center){
63 super(center);
64 }
65
66 /**
67 * @return A human readable representation of the object.
68 */
69 public final String toString() {
70 return "leaf(" + SNo + " " + Arrays.deepToString(minMax) + ")";
71 }
72
73 /**
74 * This holds the real minimum and maximum values of this hyperrectangle.
75 * Used to confirm a query belongs to this hyperrectangle. As queries might
76 * get smaller during the course of a match, this functionality is necessary
77 */
78 private float[][] minMax;
79
80 /**
81 * @return the min max values of this hyper rectangle.
82 */
83 public final float[][] getMinMax() {
84 return minMax;
85 }
86
87 /**
88 * sets the min max values of this hyper rectangle.
89 * @param minMax
90 * new min max values of this hyper rectangle.
91 */
92 public final void setMinMax(float[][] minMax) {
93 this.minMax = minMax;
94 }
95
96 /**
97 * @return min
98 */
99 public final double[] getA() {
100 return min;
101 }
102
103 /**
104 * Sets min.
105 * @param a
106 * new min
107 */
108 public final void setA(double[] a) {
109 this.min = a;
110 }
111
112 /**
113 * @return width
114 */
115 public final double[] getWidth() {
116 return width;
117 }
118
119 /**
120 * Sets width.
121 * @param b
122 * new width
123 */
124 public final void setWidth(double[] b) {
125 this.width = b;
126 int i = 0;
127 while (i < b.length) {
128 width[i] = 1 / width[i];
129 i++;
130 }
131 }
132
133 /**
134 * @return exp values for all dimensions
135 */
136 public final double[] getExp() {
137 return exp;
138 }
139
140 /**
141 * Set new exp values for the dimensions.
142 * @param e
143 * new exp values for the dimensions
144 */
145 public final void setExp(double[] e) {
146 this.exp = e;
147 }
148
149 /**
150 * @return gets the space number
151 */
152 public final int getSNo() {
153 return SNo;
154 }
155
156 /**
157 * Sets the space number of this method.
158 * @param no
159 * new space number
160 */
161 public final void setSNo(int no) {
162 SNo = no;
163 }
164
165 /**
166 * @return always returns true because this is a leaf node.
167 */
168 public final boolean isLeafNode() {
169 return true;
170 }
171
172 /**
173 * @param value
174 * Point to search
175 * @return this if the given value is inside this space
176 */
177 public final SpaceTreeLeaf search(final float[] value) {
178 assert pointInside(value);
179 // we are in the leaf, we are done
180 return this;
181 }
182
183 /**
184 * Normalizes the given tuple, puts the result in "result".
185 * @param value
186 * (tuple to be normalized)
187 * @param result
188 * (the resulting tuple)
189 */
190 public final void normalize(final float[] value, final float[] result) {
191 assert pointInside(value);
192 int i = 0;
193 while (i < value.length) {
194 result[i] = normalizeAux(value[i], i);
195 assert result[i] >= 0;
196 assert result[i] <= 1;
197 i++;
198 }
199 }
200
201 /**
202 * Normalizes the given value in dimension i.
203 * @param value
204 * Value to normalize.
205 * @param i
206 * Dimension
207 * @return Normalized version of the value in dimension i.
208 */
209 public final float normalizeAux(float value, int i) {
210 // TODO: this thing sometimes generates 1.00001 or stuff like that.
211 // shall we just force it to be 1?
212 return (float) Math.pow((value - min[i]) * width[i], exp[i]);
213 }
214
215 /**
216 * Takes a query rectangle and returns all the spaces that intersect with
217 * it. Since this object is a leaf we just add ourselves to the list
218 * @param query
219 * the query to be searched
220 * @param result
221 * will hold all the spaces that intersect with the query
222 */
223 public final void searchRange(final float[][] query,
224 float[] center, List < SpaceTreeLeaf > result) {
225 assert intersects(query); // this has to be true
226 // if (intersects(query)) {
227 result.add(this);
228 // }
229 }
230
231 /**
232 * Returns true if the given query intersects with this hyperrectangle.
233 * @param query
234 * @return true if the given query intersects with this hyperrectangle
235 */
236 public final boolean intersects(float[][] query) {
237 boolean res = true;
238 assert query.length == minMax.length;
239 int i = 0;
240 while (i < query.length && res == true) {
241 res = intersectsAux(minMax[i], query[i]);
242 i++;
243 }
244 return res;
245 }
246
247 /**
248 * Function used by {@link #intersects(float[][])} to find if any two
249 * dimension ranges are overlapping or not.
250 * @param space
251 * the dimension range of the space
252 * @param query
253 * the dimension range of the query
254 * @return true if space and query intersect
255 */
256 private boolean intersectsAux(float[] space, float[] query) {
257 assert space.length == 2;
258 assert query.length == 2;
259 // calculate the only cases where no intersection is found
260 return !(query[MIN] > space[MAX] || query[MAX] < space[MIN]);
261 }
262
263 /**
264 * Returns true if the given point is inside this space.
265 * @param point
266 * point to be tested
267 * @return true if the given point is inside
268 */
269 public final boolean pointInside(final float[] point) {
270 int i = 0;
271 assert point.length == minMax.length;
272 boolean res = true;
273 while (i < point.length && res) {
274 res = minMax[i][MIN] <= point[i] && point[i] <= minMax[i][MAX];
275 i++;
276 }
277 return res;
278 }
279
280 /**
281 * Returns "" if the given point is inside this space.
282 * Used by an assert in AbstractPPTree.
283 * @param point
284 * point to be tested
285 * @return " if all the points are inside, or a string indicating the violating coordinate
286 */
287 public final String verifyPointInside(final float[] point) {
288 int i = 0;
289 assert point.length == minMax.length;
290 String msg = "";
291 while (i < point.length) {
292
293 if(! (minMax[i][MIN] <= point[i] && point[i] <= minMax[i][MAX])){
294 msg = "Violating dim: " + i + " Space: [" + minMax[i][MIN] + ", " + minMax[i][MAX] + "] " + " tulple's value: " + point[i];
295 break;
296 }
297 i++;
298 }
299 return msg;
300 }
301
302 /**
303 * Normalizes the given query to this hyperrectangle Parts of the query
304 * might return values that are greater than 1 or 0. In those cases, we
305 * "cut" the query so that this is not performed
306 * @param firstPassQuery
307 * query first pass-normalized
308 * @param result
309 * The resulting normalized query for this space.
310 */
311 public final void generateRectangle(final float[][] firstPassQuery,
312 float[][] result) {
313 int i = 0;
314 while (i < firstPassQuery.length) {
315
316 float min = firstPassQuery[i][MIN];
317 if (min < minMax[i][MIN]) {
318 min = minMax[i][MIN];
319 }
320 result[i][MIN] = normalizeAux(min, i);
321
322 float max = firstPassQuery[i][MAX];
323 if (max > minMax[i][MAX]) {
324 max = minMax[i][MAX];
325 }
326 result[i][MAX] = normalizeAux(max, i);
327
328 assert result[i][MAX] <= 1 : " Original: " + firstPassQuery[i][MAX]
329 + " Generated: " + result[i][MAX] + " \n"
330 + Arrays.deepToString(minMax);
331 assert result[i][MIN] >= 0 : " Original: " + firstPassQuery[i][MIN]
332 + " Generated: " + result[i][MIN] + " \n"
333 + Arrays.deepToString(minMax);
334 assert result[i][MIN] <= result[i][MAX] : "MIN: " + result[i][MIN]
335 + " MAX: " + result[i][MAX] + " Originals: MIN: "
336 + firstPassQuery[i][MIN] + " MAX: "
337 + firstPassQuery[i][MAX] + " \n"
338 + Arrays.deepToString(minMax);
339 i++;
340 }
341 }
342
343 /**
344 * @param spaceNumber
345 * SNo to search.
346 * @return If this object's SNo == spaceNumber we return this, otherwise we
347 * return null.
348 */
349 public final SpaceTreeLeaf searchSpace(final int spaceNumber) {
350 if (this.SNo == spaceNumber) {
351 return this;
352 } else {
353 return null;
354 }
355 }
356
357 }