-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathdocs
345 lines (303 loc) · 12.9 KB
/
docs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
bioinfo docs
Opisati zadani algoritam/problem
Zadatak je bio implementirati Cuckoo filter i testirati njegove performanse
(vrijeme izvođenja, zauzeće memorije) pomoću k-mera različitih duljina.
Te je performanse trebalo usporediti s već postojećom implementacijom filtra.
Cuckoo filter je struktura podataka slična Bloom filtru s razlikom da se iz Cuckoo filtra
elementi mogu brisati.
Iz ove strukture podataka nije moguće izvlačiti elemente već samo provjeriti,
s određenom sigurnošću, sadrži li određeni element.
Filter se sastoji od tablice koja sadrži otiske (fingerprint) elemenata.
Kako bi dobili otisak, potrebno je element provuć kroz hash funkciju te iz rezultata
izvuć određeni broj bitova. Ti se bitovi unose u filter.
Pretpostavimo li da se rezultati hash funkcija ne preklapaju za različite ulazne elemente,
ovisno o količini bitova koje ćemo izolirati za otisak elemenata, postoji mogućnost da se oni
preklapaju. Zbog toga se javljaju lažno pozitivni rezultati.
Kako se iz Cuckoo filtra mogu brisati elementi, ta je struktura podataka mnogo brža za
rad u situacijama kada nam je to važno od Bloom filtra kod kojeg se cijela struktura mora ponovno
sagraditi kada želimo izbaciti neki element.
Za testiranje performansi bilo je potrebno testirati filter s k-merama različitih duljina.
Kako je postojeća implementacija podržavala samo cjelobrojni tip podataka, a k-mere su nizovi
znakova, bilo je potrebno osmisliti enkoder znakova u cjelobrojni tip podataka.
U tu svrhu smo izradili jednostavni enkoder koji zauzima 3 bita po znaku.
Naš enkoder mapira nukleotide A, C, G i T na bitovne nizove "000", "001", "010", "011" te koristi
posebni niz "100" za pregradu. Tako se na primjer k-mer "ACGT" enkodira u jedan 64-bitni
nepredznačeni cijeli broj (uint64_t) na sljedeći način: 000..000'100'000'001'010'011.
Ovim postupkom možemo umetnuti jedinstvene k-mere koje sadrže do 20 znakova.
Iako ovakav enkoder nije efikasan, dobro je poslužio kao baza za usporedbu s originalnom
implementacijom.
Generirane 20-mere u obliku znakovnih nizova pretvaramo u cjelobrojni tip podataka te
zatim ubacujemo u oba Cuckoo filtra i uspoređujemo rezultate.
Osim cijelih brojeva koje koristimo za usporedbu performansi, naša implementacija također
podržava izravno umetanje znakovnih nizova (std::string). Takav način korištenja je
nešto sporiji za određene hash funkcije jer se znakovni nizovi interno moraju pretvoriti u
cijele brojeve. Takav filter podržava neodređeno velike k-mere.
Interno smo koristili dvije implementacije za tablice Cuckoo filtra. Prva koristi
gotove STL strukture podataka. Tablica je predstavljena strukturom std::unordered_map koja sadrži
"buckete" tipa std::list.
U drugoj tablici koristimo jedan veliki niz podataka uint16_t. Bucketima se pristupa izravnim
indeksiranjem. Na početku svakog bucketa se nalazi broj elemenata koji se nalaze u njemu.
Time brzo provjeravamo popunjenost bucketa i lako ubacujemo element na prvo slobodno mjesto.
Naš sustav nudi 4 funkcije sažimanja: MD5, SHA1, STL hash implementacija, Two independent multiply
shift (TIMS). TIMS je korišten u originalnoj implementaciji i koristi cjelobrojni tip kao ulaz.
Ulaz za MD5 i SHA1 je znakovni niz te je cjelobrojni ulaz potrebno pretvoriti u string čime
se gubi na performansama.
Primjer
U kontekstu bioinformatike i analize genoma, ova bi se struktura podataka mogla koristit
kod provjere sadrži li neki genom određene k-mere.
Za tako nešto prvo bi trebalo popuniti filtar s k-merama iz genoma te bi vjerojatno trebali
imati više filtera za k-mere različitih duljina.
Nakon toga bi mogli jako brzo provjeravati sadrži li uneseni genom određenu k-meru koja nam je zanimljiva.
Zaključak
Ako pogledamo izvorni kod postojeće implementacije filtra, možemo vidjeti vrlo visoku razinu
optimizacije koda pa ne čudi da je naša implementacija za red veličine sporija.
Također, kako enkoder radi samo za kmere veličine 20 i manje, 50-mere, 100-mere i 200-mere
se obrađuju kao stringovi, što je sporije od baratanja s integerima.
Naša implementacija:
Napomena: sva testiranja obavljena su sa fingerprintom veličine 8 bitova.
Prosječno zauzeće memorije:
k broj k-mera tablica hash vrijeme (sec)
***MARK***
Brzina unosa:
k broj k-mera tablica hash vrijeme (sec)
10 48k single TIMS
10 48k single MD5
10 48k single SHA1
10 644k single TIMS
10 644k single MD5
10 644k single SHA1
20 1M single TIMS
20 1M single MD5
20 1M single SHA1
50 1M single TIMS
50 1M single MD5
50 1M single SHA1
100 1M single TIMS
100 1M single MD5
100 1M single SHA1
200 1M single TIMS
200 1M single MD5
200 1M single SHA1
10 48k compact TIMS 0.0068
10 48k compact MD5 0.0387
10 48k compact SHA1 0.0367
10 644k compact TIMS 0.0575
10 644k compact MD5 0.4761
10 644k compact SHA1 0.4468
20 1M compact TIMS 0.1198
20 1M compact MD5 0.8761
20 1M compact SHA1 0.7997
50 1M compact TIMS 0.2641
50 1M compact MD5 0.6698
50 1M compact SHA1 0.6812
100 1M compact TIMS 0.2860
100 1M compact MD5 0.8896
100 1M compact SHA1 0.7945
200 1M compact TIMS 0.3229
200 1M compact MD5 1.0362
200 1M compact SHA1 1.1326
Brzina provjere uspješnog unosa elemenata:
k broj k-mera tablica hash vrijeme (sec)
10 48k single TIMS
10 48k single MD5
10 48k single SHA1
10 644k single TIMS
10 644k single MD5
10 644k single SHA1
20 1M single TIMS
20 1M single MD5
20 1M single SHA1
50 1M single TIMS
50 1M single MD5
50 1M single SHA1
100 1M single TIMS
100 1M single MD5
100 1M single SHA1
200 1M single TIMS
200 1M single MD5
200 1M single SHA1
10 48k compact TIMS 0.0016
10 48k compact MD5 0.0144
10 48k compact SHA1 0.0195
10 644k compact TIMS 0.0269
10 644k compact MD5 0.2021
10 644k compact SHA1 0.1898
20 1M compact TIMS 0.0595
20 1M compact MD5 0.3631
20 1M compact SHA1 0.4118
50 1M compact TIMS 0.2481
50 1M compact MD5 0.2486
50 1M compact SHA1 0.2574
100 1M compact TIMS 0.2548
100 1M compact MD5 0.3577
100 1M compact SHA1 0.3315
200 1M compact TIMS 0.3413
200 1M compact MD5 0.6430
200 1M compact SHA1 0.4992
Postotak lažno pozitivnih elemenata:
k broj broj tablica hash false positives (%)
unesenih nepostojecih
k-mera k-mera
10 48k 5k single TIMS
10 48k 5k single MD5
10 48k 5k single SHA1
10 644k 397k single TIMS
10 644k 397k single MD5
10 644k 397k single SHA1
20 1M 500k single TIMS
20 1M 500k single MD5
20 1M 500k single SHA1
50 1M 500k single TIMS
50 1M 500k single MD5
50 1M 500k single SHA1
100 1M 500k single TIMS
100 1M 500k single MD5
100 1M 500k single SHA1
200 1M 500k single TIMS
200 1M 500k single MD5
200 1M 500k single SHA1
10 48k 500k compact TIMS 0.02102
10 48k 500k compact MD5 0.02102
10 48k 500k compact SHA1 0.04204
10 644k 500k compact TIMS 0.2332
10 644k 500k compact MD5 0.4782
10 644k 500k compact SHA1 0.4782
20 1M 500k compact TIMS 0.7310
20 1M 500k compact MD5 0.7606
20 1M 500k compact SHA1 0.7659
50 1M 500k compact TIMS 0.7566
50 1M 500k compact MD5 0.7330
50 1M 500k compact SHA1 0.7476
100 1M 500k compact TIMS 0.7522
100 1M 500k compact MD5 0.7384
100 1M 500k compact SHA1 0.7464
200 1M 500k compact TIMS 0.7218
200 1M 500k compact MD5 0.7366
200 1M 500k compact SHA1 0.7359
Razlog malog broja false positives kod tablice SingleTable je taj što se ona proširuje u ovisnosti o broju
unešenih elemenata.
Brisanje svih elemenata iz tablice:
k broj k-mera tablica hash vrijeme (sec)
10 48k single TIMS
10 48k single MD5
10 48k single SHA1
10 644k single TIMS
10 644k single MD5
10 644k single SHA1
20 1M single TIMS
20 1M single MD5
20 1M single SHA1
50 1M single TIMS
50 1M single MD5
50 1M single SHA1
100 1M single TIMS
100 1M single MD5
100 1M single SHA1
200 1M single TIMS
200 1M single MD5
200 1M single SHA1
10 48k compact TIMS 0.00305
10 48k compact MD5 0.01462
10 48k compact SHA1 0.01434
10 644k compact TIMS 0.04864
10 644k compact MD5 0.2037
10 644k compact SHA1 0.1904
20 1M compact TIMS 0.07315
20 1M compact MD5 0.3782
20 1M compact SHA1 0.3697
50 1M compact TIMS 0.2418
50 1M compact MD5 0.2401
50 1M compact SHA1 0.2658
100 1M compact TIMS 0.2479
100 1M compact MD5 0.3486
100 1M compact SHA1 0.4634
200 1M compact TIMS 0.3281
200 1M compact MD5 0.5878
200 1M compact SHA1 0.5139
Postojeća implementacija
Prosječno zauzeće memorije:
Brzina unosa:
fingerpint k broj k-mera tablica hash vrijeme (sec)
(bitovi)
8 10 644k Single TIMS 0.0099
16 10 644k Single TIMS 0.0116
8 20 1M Single TIMS 0.0402
16 20 1M Single TIMS 0.0431
8 10 644k Single SimpleTab 0.0129
16 10 644k Single SimpleTab 0.0183
8 20 1M Single SimpleTab 0.0387
16 20 1M Single SimpleTab 0.0422
8 10 644k Packed TIMS 0.0242
16 10 644k Packed TIMS x
8 20 1M Packed TIMS 0.0902
16 20 1M Packed TIMS x
8 10 644k Packed SimpleTab 0.0281
16 10 644k Packed SimpleTab x
8 20 1M Packed SimpleTab 0.0948
16 20 1M Packed SimpleTab x
* retci s 'x' - status CuckooFiltra dojavlja da nijedan element nije unesen
Brzina provjere uspješnog unosa elemenata:
fingerpint k broj k-mera tablica hash vrijeme (sec) pronadeno (%)
(bitovi)
8 10 644k Single TIMS x x
16 10 644k Single TIMS x x
8 20 1M Single TIMS x x
16 20 1M Single TIMS x x
8 10 644k Single SimpleTab x x
16 10 644k Single SimpleTab x x
8 20 1M Single SimpleTab x x
16 20 1M Single SimpleTab x x
8 10 644k Packed TIMS 0.0139 88.6
16 10 644k Packed TIMS x x
8 20 1M Packed TIMS 0.022 83.4
16 20 1M Packed TIMS x x
8 10 644k Packed SimpleTab 0.0177 88.0
16 10 644k Packed SimpleTab x x
8 20 1M Packed SimpleTab 0.0254 83.3
16 20 1M Packed SimpleTab x x
* retci s 'x' - ili nije pronaden nijedan ili uopce nije niti bio unesen nijedan element
Postotak lažno pozitivnih elemenata:
fingerpint k broj k-mera tablica hash FP rate (%)
(bitovi)
8 10 500k Single TIMS 98.3
16 10 500k Single TIMS 99.99
8 20 500k Single TIMS 97.03
16 20 500k Single TIMS 99.98
8 10 500k Single SimpleTab 98.1
16 10 500k Single SimpleTab 99.99
8 20 500k Single SimpleTab 97.07
16 20 500k Single SimpleTab 99.99
8 10 500k Packed TIMS 97.5
16 10 500k Packed TIMS x
8 20 500k Packed TIMS 96.96
16 20 500k Packed TIMS x
8 10 500k Packed SimpleTab 97.5
16 10 500k Packed SimpleTab x
8 20 500k Packed SimpleTab 97.02
16 20 500k Packed SimpleTab x
* retci s 'x' - nijedan element nije bio ubacen u tablicu
Brisanje svih elemenata iz tablice:
fingerpint k broj k-mera tablica hash vrijeme (sec)
(bitovi)
8 10 644k Single TIMS 0.0108
16 10 644k Single TIMS 0.0103
8 20 1M Single TIMS 0.0219
16 20 1M Single TIMS 0.0194
8 10 644k Single SimpleTab 0.0167
16 10 644k Single SimpleTab 0.0146
8 20 1M Single SimpleTab 0.0288
16 20 1M Single SimpleTab 0.0238
8 10 644k Packed TIMS 0.0259
16 10 644k Packed TIMS x
8 20 1M Packed TIMS 0.0448
16 20 1M Packed TIMS x
8 10 644k Packed SimpleTab 0.0296
16 10 644k Packed SimpleTab x
8 20 1M Packed SimpleTab 0.0483
16 20 1M Packed SimpleTab x
* retci s 'x' - nijedan element nije bio ubacen u tablicu
Literatura
Cuckoo Filter: Practically Better Than Bloom, https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf
Cuckoo Filters, https://mybiasedcoin.blogspot.com/2014/10/cuckoo-filters.html
cuckoofilter, https://github.com/efficient/cuckoofilter
Dietzfelbinger M. (1996) Universal hashing and k-wise independent random variables via integer arithmetic without primes. In: Puech C., Reischuk R. (eds) STACS 96. STACS 1996. Lecture Notes in Computer Science, vol 1046. Springer, Berlin, Heidelberg