Bloom filter

Uji keanggotaan yang tidak menyimpan anggotanya. Tanyakan apakah sesuatu ada di dalam set, dan ia menjawab “pasti tidak ada” atau “mungkin ada” — dan ia hanya bisa salah pada arah yang kedua.

Di mana ini benar-benar dipakai

Cassandra, HBase, dan LevelDB menyimpan satu filter ini di memory untuk setiap file di disk. Sebelum membaca file untuk mencari sebuah key, mereka bertanya dulu ke filter. Jawaban “tidak” adalah bukti, jadi pembacaannya dilewati sama sekali; jawaban “ya” berbiaya satu pembacaan yang mungkin tidak menemukan apa pun. Sebagian besar lalu lintas disk lenyap, dan karena “tidak” tidak pernah salah, tidak ada key yang terlewat.

Jaminannya

Item yang sudah di-insert tidak akan pernah dijawab “tidak ada” — insert hanya menyalakan bit, dan tidak ada yang pernah memadamkannya. Ini struktural, bukan statistik: bukan hampir tidak pernah, tapi tidak pernah.

Cara kerjanya

m bit, k hash. Insert menyalakan k bit. Query menjawab “possibly present” hanya jika seluruh k bit menyala.

Burton H. Bloom, CACM 13(7), 1970

Mulai dari siniGeser slider memory ke kiri sampai rate false positive mulai naik — lalu lihat jumlah false negative di sebelahnya. Ia tetap nol sepanjang jalan turun.

Satu item, dari awal sampai akhir

Sebelum semua kontrol di bawah: inilah seluruh mekanismenya, pada ukuran yang bisa Anda hitung. 64 bit, 3 hash, dimulai dari kosong.

1 dari 12

Item di-hash dua kali

item-0 → h₁ = 3,357,449,650, h₂ = 2,355,847,969

Dua bilangan 32-bit, dari MurmurHash3 dengan dua seed berbeda. Item yang sama, angka yang sama, setiap saat dan di mesin mana pun — determinisme itulah yang membuat kita bisa menanyakan item yang sama nanti.

k nomor slot diturunkan dari keduanya

slot yang dialamatkan item ini
g₀	(3,357,449,650 + 0×2,355,847,969) mod 64	= 50	baru diset
g₁	(3,357,449,650 + 1×2,355,847,969) mod 64	= 19	baru diset
g₂	(3,357,449,650 + 2×2,355,847,969) mod 64	= 52	baru diset

gᵢ(x) = h₁(x) + i·h₂(x), diambil mod m agar jatuh di dalam array. Dua hash menghasilkan k slot: Kirsch & Mitzenmacher (ESA 2006) menunjukkan keduanya berperilaku seperti k hash independen, itulah sebabnya batas error-nya tetap berlaku.

Bit-bit itu diset · 3 bit menyala

0000000000000000000100000000000000000000000000000010100000000000

Tidak ada yang pernah dihapus. Itulah sebabnya item yang sudah dimasukkan tidak akan pernah dijawab “tidak ada”.

Gunakan hash yang sengaja dibuat buruk

Stream

Distribusiseberapa sering item berulang — data nyata tidak pernah uniformSetiap item sama mungkinnya. Kasus yang menjadi dasar bound di buku teks.

Item distinctberapa banyak item berbeda yang tersedia untuk diambilPanjang streamberapa banyak item yang melewati struktur iniSeedmengubah hash, dan karenanya item mana yang kebetulan bertabrakan

k — hashdi berapa tempat dalam array setiap item dicatatk = (m/n)·ln 2

Tautan ini membawa stream dan seluruh parameter. Tanpa server, tanpa akun — state-nya ikut di dalam URL.

Memory

berapa banyak memory yang diberikan ke filter — makin banyak bit, makin sedikit jawaban salah

m — bit65,536 bits · 8.0 KiB

Geser untuk mengubah ukuran bit array. Predicted dan measured error bergerak bersama.

Apakah angka itu mengejutkan?

Rate terukur di atas adalah satu penarikan. Berikut konfigurasi yang sama dijalankan 24 kali, masing-masing dengan seed berbeda — stream berbeda dan probe berbeda, persis seperti yang dilakukan tombol “seed +1” satu tekan sekali.