Kalkulator parameter
Bekerja mundur. Sebutkan berapa item yang Anda perkirakan dan berapa error yang bisa Anda terima, lalu ini memberi Anda struktur yang harus dibangun dan berapa biayanya dalam memory.
Di mana ini benar-benar dipakai
Beginilah cara ukurannya ditentukan dalam praktik. Tidak ada yang memilih jumlah bit secara langsung — orang tahu kira-kira berapa item yang akan datang dan berapa error rate yang sanggup diserap sistemnya, lalu ukurannya keluar dari sebuah rumus. Kedua rumusnya ditampilkan di sini, bukan hanya hasilnya.
Cara kerjanya
Sebutkan yang Anda harapkan dan yang bisa Anda toleransi. Dapatkan struktur yang harus dibangun, rumus asalnya, dan berapa biayanya.
Parameter
Bloom filter
m — bit
9,585,059
k — hash
7
Memory
1.14 MiB
Bit per item
9.59
Prediksi
1.00%
Dibanding struktur exact
13.4×
Set exact dengan n yang sama, pada 16 byte per key, akan memakan 15.26 MiB
Bagaimana angka itu didapat
m = −n·ln ε / (ln 2)²
= −1,000,000 × (−4.6052) / 0.4805
= 9,585,059 bits
ln ε bernilai negatif, jadi tanda minus membuat m positif: ε yang lebih kecil berarti m yang lebih besar. (ln 2)² datang dari kondisi array terisi setengah pada titik optimum — tingkat keterisian yang menyeimbangkan “lebih banyak bit menyala berarti lebih banyak bukti” dengan “lebih banyak bit menyala berarti lebih banyak kebetulan”.
k = (m/n)·ln 2
= (9,585,059 / 1,000,000) × 0.6931
= 7 hashes
k punya titik optimum, bukan makin banyak makin baik: setiap hash tambahan adalah satu peluang lagi untuk menangkap item yang tidak ada, sekaligus satu bit lagi yang menyala pada setiap insert. Keduanya berpotongan di (m/n)·ln 2, yaitu k yang mengisi array tepat setengah.
Ukuran dibulatkan ke atas ke bit utuh, counter utuh, atau pangkat dua berikutnya, sehingga error yang diberikan selalu setidaknya sebaik target — tidak pernah lebih buruk.
Burton H. Bloom, CACM 13(7), 1970
Count-Min sketch
w — width
272
d — depth
5
Memory
5.3 KiB
1,360 × Uint32
Overestimate dibatasi ε·N
1.00% × N
Error-nya aditif terhadap seluruh stream, bukan terhadap count item itu sendiri. Item langka dalam stream panjang bisa di-overestimate jauh melebihi kemunculan sebenarnya.
Bagaimana angka itu didapat
w = ⌈e/ε⌉
= ⌈2.7183 / 0.01⌉
= 272 columns
e muncul karena batasnya adalah argumen pertidaksamaan Markov atas ekspektasi massa collision dalam satu baris; e/ε adalah lebar di mana ekspektasi overestimate turun di bawah ε·N.
d = ⌈ln(1/δ)⌉
= ⌈ln(1 / 0.01)⌉ = ⌈4.6052⌉
= 5 rows
Setiap baris adalah estimasi independen yang hanya bisa terlalu tinggi. Baris-baris gagal secara independen, jadi d baris gagal bersamaan dengan probabilitas paling banyak (1/e)^d — buat itu di bawah δ dan Anda dapat d = ln(1/δ).
Ukuran dibulatkan ke atas ke bit utuh, counter utuh, atau pangkat dua berikutnya, sehingga error yang diberikan selalu setidaknya sebaik target — tidak pernah lebih buruk.
Cormode & Muthukrishnan, J. Algorithms 55(1), 2005
HyperLogLog
p — presisi
12
m — register
4,096
Memory
4.0 KiB
satu byte per register — jika dipadatkan ke 6 bit, implementasi nyata memakai 25% lebih sedikit
Standard error 1.04/√m
1.63%
Dibanding struktur exact
3906×
Set exact dengan n yang sama, pada 16 byte per key, akan memakan 15.26 MiB
Bagaimana angka itu didapat
m = (1.04/σ)²
= (1.04 / 0.02)² = 2704
= 4,096 registers (2^12)
Standard error estimator-nya 1.04/√m, jadi jumlah register yang dibutuhkan tumbuh dengan kuadrat akurasi yang diinginkan: menyetengahkan error berbiaya empat kali lipat memory.
σ = 1.04/√m
= 1.04 / √4,096
= 1.63%
m harus pangkat dua karena indeks register dibaca dari p bit teratas hash. Karena itu precision dibulatkan ke atas, dan error yang didapat sedikit lebih baik daripada yang diminta.
Flajolet, Fusy, Gandouet & Meunier, AofA 2007
Perhatikan apa yang tidak ada: n. Memory HyperLogLog tidak bergantung pada berapa banyak item yang Anda perkirakan. 16 KiB yang sama menghitung seribu nilai distinct atau semiliar, dan hanya error relatifnya yang tetap.
Cuckoo filter
f — bit fingerprint
10
Bucket
524,288
× 4 entry per bucket
Memory
4.00 MiB
byte utuh per entry — jika dipadatkan ke f bit, implementasi nyata memakai lebih sedikit
Kapasitas
1,992,294
insert ditolak setelah ini, bukan diturunkan kualitasnya
Bagaimana angka itu didapat
f = ⌈log₂(2b/ε)⌉
= ⌈log₂(2×4 / 0.01)⌉
= 10 bits
Setiap bucket menampung b fingerprint dan sebuah query memeriksa dua bucket, jadi item yang tidak ada punya sekitar 2b peluang untuk cocok dengan salah satu dari 2^f fingerprint yang mungkin.
buckets = 2^⌈log₂(n/αb)⌉
= 2^⌈log₂(1,000,000 / (α × 4))⌉
= 524,288
Ukuran dibulatkan ke atas ke bit utuh, counter utuh, atau pangkat dua berikutnya, sehingga error yang diberikan selalu setidaknya sebaik target — tidak pernah lebih buruk.
Fan, Andersen, Kaminsky & Mitzenmacher, CoNEXT 2014
Bit per item ideal, dipadatkan
Cuckoo 10.53 · Bloom 9.59
Pada ε ini Bloom butuh lebih sedikit bit. Cuckoo melampauinya di bawah sekitar ε = 0,2%.