View Javadoc

1   package net.obsearch.dimension;
2   import net.obsearch.exception.IllegalIdException;
3   import net.obsearch.exception.OBException;
4   import net.obsearch.ob.OBDouble;
5   import net.obsearch.Index;
6   import java.util.Random;
7   import net.obsearch.exception.OBStorageException;
8   import cern.colt.list.LongArrayList;
9   import java.util.LinkedList;
10  import java.util.Iterator;
11  import java.util.List;
12  /*
13  		OBSearch: a distributed similarity search engine This project is to
14   similarity search what 'bit-torrent' is to downloads. 
15      Copyright (C) 2008 Arnoldo Jose Muller Molina
16  
17    	This program is free software: you can redistribute it and/or modify
18      it under the terms of the GNU General Public License as published by
19      the Free Software Foundation, either version 3 of the License, or
20      (at your option) any later version.
21  
22      This program is distributed in the hope that it will be useful,
23      but WITHOUT ANY WARRANTY; without even the implied warranty of
24      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25      GNU General Public License for more details.
26  
27      You should have received a copy of the GNU General Public License
28      along with this program.  If not, see <http://www.gnu.org/licenses/>.
29  */
30  
31  /** 
32  	*  DimensionDouble Stores objects of type double.
33  	*  
34    *  @author      Arnoldo Jose Muller Molina    
35    */
36  		 public class DimensionDouble extends AbstractDimension implements Comparable<DimensionDouble>{
37  				 
38  				 /**
39  					* The value of type double of the dimension;
40  					*/
41  				 private double value;
42  				 
43  				 /**
44  					* Creates a new DimensionDouble object.
45            * @param position The position of this dimension.
46            * @param value The value of this dimension.
47  					*/
48  				 public DimensionDouble(int position, double value){
49  				     super(position);
50  						 this.value = value;
51  				 }
52  
53  				 /**
54  					* Creates a dimension array from the given pivots and the given object.
55  					* @param pivots The pivots used for the embedding.
56  					* @param object The object to be projected.
57  					* @return A new dimension array.
58  					*/
59  				 public static DimensionDouble[] getTuple(OBDouble[] pivots, OBDouble object
60             ) throws 
61              IllegalIdException, IllegalAccessException, InstantiationException,
62              OBException
63  
64      {
65          DimensionDouble[]  res = new DimensionDouble [pivots.length];
66          int i = 0;
67          for (OBDouble p : pivots) {
68              res[i] = new DimensionDouble(i, p.distance(object));
69              i++;
70          }
71          return res;
72      }
73  
74    
75     
76  
77  	/**
78  	 * Selects k random elements from the given source.
79  	 * 
80  	 * @param k
81  	 *            number of elements to select
82  	 * @param r
83  	 *            Random object used to randomly select objects.
84  	 * @param source
85  	 *            The source of item ids.
86  	 * @param index
87  	 *            underlying index.
88  	 * @param will
89  	 *            not add pivots included in excludes.
90     * @param minDistance The min distance required by the objects.
91  	 * @return The ids of selected objects.
92  	 */
93  	public static long[] select(int k, Random r, LongArrayList source,
94  															Index<OBDouble> index, LongArrayList excludes, double minDistance) throws IllegalIdException, OBException, IllegalAccessException, InstantiationException {
95  		int max = max(source, index);
96  		long[] res = new long[k];
97  		int i = 0;
98  		List<Long> l = new LinkedList<Long>();
99  		
100 		while (i < res.length) {
101 			long id = mapId(r.nextInt(max), source);
102 			if ((excludes == null || !excludes.contains(id)) && minDistance(l, index) > minDistance ) {
103 				res[i] = id;
104 				l.add(id);
105 			} else {
106 				l.remove(l.size() -1);
107 				continue; // repeat step.
108 			}
109 			i++;
110 		}
111 		return res;
112 	}
113 
114 
115 	
116 
117 	/**
118    * Calculate the minimum distance of the given objects (all objects
119    * compared against all objects)
120    * @param objects
121    * @return the min distance
122    */ 
123   public static double minDistance(List<Long> objects, Index<OBDouble> index)throws IllegalIdException, OBException, IllegalAccessException, InstantiationException{
124 			double res = Double.MAX_VALUE;
125 			Iterator<Long> it = objects.iterator();
126 			for(long l1 : objects){
127 					for(long l2 : objects){
128 							if(l1 == l2){
129 									continue;
130 							}
131 							res = (double)Math.min(res, index.getObject(l1).distance(index.getObject(l2)));
132 					}
133 			}
134 			return res;
135 	}
136 
137 				 /**
138 					* Creates a double array from the given pivots and the given object.
139 					* @param pivots The pivots used for the embedding.
140 					* @param object The object to be projected.
141 					* @return A new double array.
142 					*/
143 				  public static double[] getBasicTuple(OBDouble[] pivots, OBDouble object
144            ) throws 
145             IllegalIdException, IllegalAccessException, InstantiationException,
146             OBException
147 
148     {
149         double[]  res = new double [pivots.length];
150         int i = 0;
151         for (OBDouble p : pivots) {
152             res[i] =  p.distance(object);
153             i++;
154         }
155         return res;
156     }
157 
158 				 /**
159 					* Creates a dimension array from the given pivots and the given
160 					* object id. Loads the objects from the DB.
161 					*/
162 				  public static DimensionDouble[] getTuple(long[] pivots, long objectId,
163 																				 Index<? extends OBDouble>  index) throws 
164             IllegalIdException, IllegalAccessException, InstantiationException,
165 							OBException{
166 							DimensionDouble[]  res = new DimensionDouble [pivots.length];
167 							OBDouble o = index.getObject(objectId);
168 							int i = 0;
169 							for(long pivotId : pivots){
170 									res[i] = new DimensionDouble(i, index.getObject(pivotId).distance(o));
171 									i++;
172 							}
173 							return res;
174 					}
175 
176 					
177 
178 					/**
179 					 * Compares this object with other. 
180 					 */
181 					public int compareTo(DimensionDouble other){
182 							if(value < other.value){
183 									return -1;
184 							}else if(value > other.value){
185 									return 1;
186 							}else{
187 									return 0;
188 							}
189 					}
190 
191 
192 					public double getValue(){
193 							return value;
194 					}
195 
196 
197 
198 		/**
199      * Calculates the smap tuple for the given objectId, and the given pivots
200      * @param pivots
201      * @param objectId
202      * @return
203      */
204     public static double[] getPrimitiveTuple(long[] pivots, long objectId,
205             Index<? extends OBDouble>  index) throws 
206             IllegalIdException, IllegalAccessException, InstantiationException,
207             OBException
208 
209     {
210         double[] res = new double[pivots.length];
211         int i = 0;
212         OBDouble o = index.getObject(objectId);
213         for (long pivotId : pivots) {
214             res[i] = index.getObject(pivotId).distance(o);
215             i++;
216         }
217         return res;
218     }
219 
220 		/**
221 		 * Transform the given primitive tuple into a Dimension tuple.
222 		 * @param tuple The tuple that will be transformed.
223 		 * @return A DimensionDouble of dimensions.
224 		 */
225 		public static DimensionDouble[] transformPrimitiveTuple(double[] tuple){
226 				DimensionDouble[] res = new DimensionDouble[tuple.length];
227 				int i = 0;
228 				while(i < tuple.length){
229 						res[i] = new DimensionDouble(i, tuple[i]);
230 						i++;
231 				}
232 				return res;
233 		}
234     
235 
236     /**
237      * Calculates the smap tuple for the given objectId, and the given pivots
238      * @param pivots
239      * @param objectId
240      * @return
241      */
242     public static double[] getPrimitiveTuple(OBDouble[] pivots, OBDouble object
243            ) throws 
244             IllegalIdException, IllegalAccessException, InstantiationException,
245             OBException
246 
247     {
248         double[] res = new double[pivots.length];
249         int i = 0;
250         for (OBDouble p : pivots) {
251             res[i] = p.distance(object);
252             i++;
253         }
254         return res;
255     }
256     
257     /**
258      * Calculates L-inf for two double tuples.
259      * @param a  tuple
260      * @param b tuple
261      * @return L-infinite for a and b.
262      */
263     public static double lInfinite(double[] a, double[] b){
264         assert a.length == b.length;
265         double max = Double.NEGATIVE_INFINITY 
266 ;
267         int i = 0;
268         while(i < a.length){
269             // double t = (double)Math.abs(a[i]  - b[i]);
270 						double t = (double)(a[i]  - b[i]);
271 						t = t < 0 ? (double)-t : t;
272             if(t > max){
273                 max = t;
274             }
275             i++;
276         }
277         return max;
278     }
279 
280 
281 		/**
282      * Calculates the euc distance for two tuples
283      * @param a  tuple
284      * @param b tuple
285      * @return L-infinite for a and b.
286      */
287     public static double euclidean(double[] a, double[] b){
288         assert a.length == b.length;
289         double result = 0;
290 				int i = 0;
291         while(i < a.length){
292             double j = a[i] - b[i];
293             result += j * j;
294             i++;
295         }
296         return (double)Math.sqrt(result);
297     }
298 
299 		 }
300 
301