1 package net.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(double[] 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 double[][] minMax;
79
80 /**
81 * @return the min max values of this hyper rectangle.
82 */
83 public final double[][] 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(double[][] 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 double[] 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 double[] value, final double[] 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 double normalizeAux(double 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 double res = (double) Math.pow((value - min[i]) * width[i], exp[i]);
213 if(res > 1){
214 res = 1;
215 }
216 if(res < 0){
217 res = 0;
218 }
219 return res;
220 }
221
222 /**
223 * Takes a query rectangle and returns all the spaces that intersect with
224 * it. Since this object is a leaf we just add ourselves to the list
225 * @param query
226 * the query to be searched
227 * @param result
228 * will hold all the spaces that intersect with the query
229 */
230 public final void searchRange(final double[][] query,
231 double[] center, List < SpaceTreeLeaf > result) {
232 assert intersects(query); // this has to be true
233 // if (intersects(query)) {
234 result.add(this);
235 // }
236 }
237
238 /**
239 * Returns true if the given query intersects with this hyperrectangle.
240 * @param query
241 * @return true if the given query intersects with this hyperrectangle
242 */
243 public final boolean intersects(double[][] query) {
244 boolean res = true;
245 assert query.length == minMax.length;
246 int i = 0;
247 while (i < query.length && res == true) {
248 res = intersectsAux(minMax[i], query[i]);
249 i++;
250 }
251 return res;
252 }
253
254 /**
255 * Function used by {@link #intersects(double[][])} to find if any two
256 * dimension ranges are overlapping or not.
257 * @param space
258 * the dimension range of the space
259 * @param query
260 * the dimension range of the query
261 * @return true if space and query intersect
262 */
263 private boolean intersectsAux(double[] space, double[] query) {
264 assert space.length == 2;
265 assert query.length == 2;
266 // calculate the only cases where no intersection is found
267 return !(query[MIN] > space[MAX] || query[MAX] < space[MIN]);
268 }
269
270 /**
271 * Returns true if the given point is inside this space.
272 * @param point
273 * point to be tested
274 * @return true if the given point is inside
275 */
276 public final boolean pointInside(final double[] point) {
277 int i = 0;
278 assert point.length == minMax.length;
279 boolean res = true;
280 while (i < point.length && res) {
281 res = minMax[i][MIN] <= point[i] && point[i] <= minMax[i][MAX];
282 i++;
283 }
284 return res;
285 }
286
287 /**
288 * Returns "" if the given point is inside this space.
289 * Used by an assert in AbstractPPTree.
290 * @param point
291 * point to be tested
292 * @return " if all the points are inside, or a string indicating the violating coordinate
293 */
294 public final String verifyPointInside(final double[] point) {
295 int i = 0;
296 assert point.length == minMax.length;
297 String msg = "";
298 while (i < point.length) {
299
300 if(! (minMax[i][MIN] <= point[i] && point[i] <= minMax[i][MAX])){
301 msg = "Violating dim: " + i + " Space: [" + minMax[i][MIN] + ", " + minMax[i][MAX] + "] " + " tulple's value: " + point[i];
302 break;
303 }
304 i++;
305 }
306 return msg;
307 }
308
309 /**
310 * Normalizes the given query to this hyperrectangle Parts of the query
311 * might return values that are greater than 1 or 0. In those cases, we
312 * "cut" the query so that this is not performed
313 * @param firstPassQuery
314 * query first pass-normalized
315 * @param result
316 * The resulting normalized query for this space.
317 */
318 public final void generateRectangle(final double[][] firstPassQuery,
319 double[][] result) {
320 int i = 0;
321 while (i < firstPassQuery.length) {
322
323 double min = firstPassQuery[i][MIN];
324 if (min < minMax[i][MIN]) {
325 min = minMax[i][MIN];
326 }
327 result[i][MIN] = normalizeAux(min, i);
328
329 double max = firstPassQuery[i][MAX];
330 if (max > minMax[i][MAX]) {
331 max = minMax[i][MAX];
332 }
333 result[i][MAX] = normalizeAux(max, i);
334
335 assert result[i][MAX] <= 1 : " Original: " + firstPassQuery[i][MAX]
336 + " Generated: " + result[i][MAX] + " \n"
337 + Arrays.deepToString(minMax);
338 assert result[i][MIN] >= 0 : " Original: " + firstPassQuery[i][MIN]
339 + " Generated: " + result[i][MIN] + " \n"
340 + Arrays.deepToString(minMax);
341 assert result[i][MIN] <= result[i][MAX] : "MIN: " + result[i][MIN]
342 + " MAX: " + result[i][MAX] + " Originals: MIN: "
343 + firstPassQuery[i][MIN] + " MAX: "
344 + firstPassQuery[i][MAX] + " \n"
345 + Arrays.deepToString(minMax);
346 i++;
347 }
348 }
349
350 /**
351 * @param spaceNumber
352 * SNo to search.
353 * @return If this object's SNo == spaceNumber we return this, otherwise we
354 * return null.
355 */
356 public final SpaceTreeLeaf searchSpace(final int spaceNumber) {
357 if (this.SNo == spaceNumber) {
358 return this;
359 } else {
360 return null;
361 }
362 }
363
364 }