View Javadoc

1   package net.obsearch.pivots.dummy;
2   
3   import net.obsearch.Index;
4   import net.obsearch.exception.OBException;
5   import net.obsearch.exception.OBStorageException;
6   import net.obsearch.exception.PivotsUnavailableException;
7   import net.obsearch.pivots.IncrementalPivotSelector;
8   import net.obsearch.pivots.PivotResult;
9   import cern.colt.list.LongArrayList;
10  /*
11  		OBSearch: a distributed similarity search engine This project is to
12   similarity search what 'bit-torrent' is to downloads. 
13      Copyright (C) 2008 Arnoldo Jose Muller Molina
14  
15    	This program is free software: you can redistribute it and/or modify
16      it under the terms of the GNU General Public License as published by
17      the Free Software Foundation, either version 3 of the License, or
18      (at your option) any later version.
19  
20      This program is distributed in the hope that it will be useful,
21      but WITHOUT ANY WARRANTY; without even the implied warranty of
22      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23      GNU General Public License for more details.
24  
25      You should have received a copy of the GNU General Public License
26      along with this program.  If not, see <http://www.gnu.org/licenses/>.
27  */
28  
29  /** 
30  	*  IncrementalFixedPivotSelector 
31  	*  
32    *  @author      Arnoldo Jose Muller Molina    
33    */
34  
35  public class IncrementalFixedPivotSelector implements IncrementalPivotSelector {
36  
37      /**
38       * Pre-computed pivot definitions
39       */	
40  	public static long[] def = { 290, 960, 35, 263, 360, 75, 619, 519, 335, 681, 332, 497, 306, 169, 281, 890, 387, 850, 971, 804};
41  
42      public static long[] levScalab = { 94323, 63655, 37558, 34472, 54433, 88958,
43              97696, 88615, 93960, 93739, 97697, 20414, 34162, 21023, 66357,
44              65775, 74077, 74498, 69404, 75965, 31607, 55316, 91240, 326, 10456,
45              41388, 64728, 39269, 63582, 54810 };
46  
47      // 30 pivots for ted
48      public static long[] ted = { 57300, 196436, 10653, 136029, 203654, 189753,
49              152060, 133273, 236109, 144716, 30129, 192050, 14036, 28810,
50              202543, 59154, 123211, 203986, 5279, 118146, 75130, 135862, 200942,
51              92282, 77436, 110657, 116055, 37261, 94338, 235642 };
52  
53      // 30 pivots + .95 (10 levels, only 9 used).
54      public static long[][] tedLevel = {
55  
56              { 15934, 107349, 18536, 159414, 187321, 80913, 109586, 55891, 9032,
57                      157372, 63619, 4363, 43993, 244702, 189550, 166295, 128207,
58                      147989, 97480, 238126, 107564, 184695, 100880, 6080,
59                      129561, 66674, 234816, 110551, 79308, 32987 },
60              { 138006, 233523, 176720, 11694, 87234, 105080, 208082, 146706,
61                      97906, 21545, 67960, 177729, 235606, 108664, 63968, 205992,
62                      234488, 214120, 74450, 123203, 96723, 112753, 9651, 136600,
63                      50675, 194891, 96263, 61289 },
64              { 108877, 141682, 4195, 165175, 119242, 36922, 7158, 213156,
65                      241849, 158081, 198049, 123730, 143313, 9963, 205958,
66                      23842, 113848, 121265, 62235, 140034, 236632, 209080,
67                      232804, 131268, 81772, 99495 },
68              { 205859, 76130, 193358, 129233, 209350, 70459, 179759, 53284,
69                      200934, 227243, 6605, 97360, 173855, 237054, 158210, 10636,
70                      178349, 216620, 216814, 100031, 131604, 109242, 213669,
71                      84933 },
72              { 137734, 111366, 239355, 49991, 174182, 96945, 48328, 35088,
73                      137863, 46953, 64300, 181846, 39215, 232845, 121960,
74                      228332, 139662, 95548, 968, 85698, 147004, 118684 },
75              { 210342, 41235, 75519, 105228, 87526, 2170, 108443, 34877, 112732,
76                      39078, 26858, 120868, 152787, 14105, 144830, 178479, 68468,
77                      194694, 129460, 18198 },
78              { 220715, 236557, 152792, 31517, 5346, 25152, 154219, 187172,
79                      34347, 199820, 53241, 95499, 48729, 163319, 65337, 138582,
80                      191089, 12606, 79032 },
81              { 170699, 121277, 26031, 27020, 43075, 110093, 231245, 176657,
82                      67649, 145891, 138798, 48040, 133480, 47006, 242678,
83                      193006, 197849, 229375 },
84              { 235654, 169269, 107349, 174847, 108031, 65633, 61768, 27618,
85                      108590, 104125, 110130, 110219, 188196, 132412, 3734,
86                      50649, 202913 },
87  
88      };
89  
90      // lev pivots (18 pivots for lev)
91  
92      // public static int [] lev = { 992515, 828447, 708572, 879139, 679767,
93      // 356148, 23230, 263566, 744140, 507502, 855677, 749056, 908433, 864534,
94      // 754452, 301782, 552141, 103224};
95      public static long[] lev = { 28968, 628464, 433184, 921379, 656225, 681704,
96              209306, 319394, 472165, 891033, 277620, 38427, 496272, 509825,
97              925880, 935531, 927760, 245884 };
98  
99      public static long[][] levLevel = {
100             { 992316, 405315, 721966, 850092, 163932, 47113, 624547, 625026,
101                     857504, 473406, 785269, 858005, 55829, 363803, 591228,
102                     814583, 299929, 683399 },
103             { 395006, 800848, 992359, 165724, 238112, 523984, 191257, 229295,
104                     229266, 757516, 73494, 541124, 301782, 555629, 624227,
105                     553970, 546464 },
106             { 355815, 517393, 429050, 344504, 282655, 490669, 466620, 539612,
107                     866049, 506134, 993156, 983808, 781464, 422685, 871406,
108                     605017 },
109             { 138781, 937714, 843316, 285526, 106044, 948402, 2098, 905359,
110                     685163, 857504, 624288, 321874, 876559, 887469, 18843 },
111             { 428597, 584831, 463252, 791267, 910050, 793711, 641866, 910218,
112                     40579, 870290, 955569, 198249, 74473, 525787 },
113             { 429041, 482882, 802292, 607524, 788646, 595296, 984845, 29348,
114                     864562, 271879, 427230, 681523, 350428 },
115             { 993205, 82115, 237862, 188255, 20414, 604416, 538071, 776840,
116                     2001, 362136, 750745, 514440 },
117             { 992537, 833676, 301971, 867517, 290161, 506692, 727581, 423088,
118                     509094, 528868, 232835 },
119             { 123279, 530530, 800734, 9878, 186602, 992663, 382075, 42792,
120                     584374, 228068 } };
121 
122     // 16 pivots for mtd
123      public static long [] mtd = {173221, 81425, 258192, 229333, 256964,
124      187123, 211523, 143917, 28954, 262061, 86748, 218554, 113214, 260088,
125      337932, 11769};
126     
127 		/*public static int[] mtd = { 143538, 191537, 27666, 207637, 234407, 278801,
128             14835, 142853, 198987, 150621, 194982, 265446, 14548, 18332, 67002,
129             133379, 55931, 290771, 306695, 19787, 317705, 269611, 241363,
130             235312, 49570, 147869, 347944, 80416, 88808, 305347, 292672, 32854 };
131 		*/
132     public static long[][] mtdLevel = {
133             { 275060, 130016, 199779, 346945, 99362, 225116, 257606, 346212,
134                     174634, 47137, 51535, 98775, 133386, 325413, 282666, 24063 },
135             { 98714, 305085, 188131, 348248, 171624, 120761, 215617, 322408,
136                     287498, 75336, 107898, 66643, 312034, 282658, 173327 },
137             { 269101, 17275, 337074, 221119, 30915, 206906, 75336, 95375,
138                     62891, 104250, 239320, 116709, 28954, 45808 },
139             { 112833, 211151, 121839, 285318, 117790, 105893, 59704, 191409,
140                     123579, 40893, 172139, 308417, 148459 },
141             { 225621, 274709, 315087, 102871, 223744, 305914, 246259, 18361,
142                     187720, 313273, 115605, 296311 },
143             { 28598, 226500, 179101, 224413, 113452, 160126, 272162, 114709,
144                     6947, 76065, 231371 },
145             { 288361, 169153, 199593, 180289, 62561, 137528, 205684, 279728,
146                     110517, 102344 },
147             { 99242, 40641, 42519, 291856, 244712, 179101, 299274, 203226,
148                     204242 },
149             { 283781, 257700, 152463, 236670, 4420, 125697, 55347, 246946 }, };
150 
151     long[][] data;
152 
153     int ind = 0; // next level
154     
155     public IncrementalFixedPivotSelector() {
156     	this(def);
157     }
158 
159     public IncrementalFixedPivotSelector(long[] ids) {
160         data = new long[1][];
161         data[0] = ids;
162     }
163 
164     public IncrementalFixedPivotSelector(long[][] ids) {
165         data = ids;
166     }
167 
168     @Override
169     public PivotResult generatePivots(int pivotCount, Index index)
170             throws OBException, IllegalAccessException, InstantiationException,
171             OBStorageException, PivotsUnavailableException {
172         return generatePivots(pivotCount, null, null);
173     }
174 
175     @Override
176     public PivotResult generatePivots(int pivotCount, LongArrayList elements,
177             Index index) throws OBException, IllegalAccessException,
178             InstantiationException, OBStorageException,
179             PivotsUnavailableException {
180         long[] res = new long[pivotCount];
181         int i = 0;
182         while (i < res.length) {
183             res[i] = data[ind][i];
184             i++;
185         }
186         ind++;
187         return new PivotResult(res);
188     }
189 
190 }