Bloom filter
Bloom filter adalah struktur data yang memungkinkan komputer untuk melihat apakah elemen yang diberikan muncul dalam suatu set. Bloom filter menggunakan fungsi hash untuk melakukan ini. Untuk setiap elemen yang ditambahkan, nilai hash dihitung. Ketika sebuah elemen baru ditambahkan, nilai hash-nya dibandingkan dengan elemen-elemen lain dalam set. Bloom filter adalah struktur data probabilistik. Adalah mungkin untuk mendapatkan positif palsu, tetapi tidak untuk mendapatkan negatif palsu. Dengan kata lain, sebuah kueri mengembalikan "mungkin dalam himpunan" atau "pasti tidak dalam himpunan". Elemen dapat ditambahkan ke himpunan, tetapi tidak dapat dihapus. Untuk setiap elemen yang ditambahkan, probabilitas mendapatkan positif palsu bertambah.
Edward Bloom mengusulkan filter Bloom pada tahun 1970. Dalam artikel tersebut, Bloom mengandaikan adanya algoritma untuk memberi tanda hubung pada kata-kata di akhir baris. Menurut contoh, sebagian besar kata memiliki pola tanda hubung yang sederhana. Tetapi sekitar 10% dari kata-kata tersebut membutuhkan pencarian yang memakan waktu untuk mengambil aturan yang benar. Kasusnya adalah kasus penghubung sekitar 500.000 kata. Dia melihat bahwa dengan menggunakan teknik hashing bebas kesalahan "normal", menyimpan pola tanda hubung, akan memerlukan banyak memori. Dia menemukan bahwa dengan menggunakan tekniknya, dia bisa menghilangkan sebagian besar pencarian. Sebagai contoh, area hash hanya 15% dari ukuran yang dibutuhkan oleh hash bebas kesalahan yang ideal masih menghilangkan 85% dari akses disk.
Secara umum, kurang dari 10 bit per elemen diperlukan untuk probabilitas positif palsu 1%, terlepas dari ukuran atau jumlah elemen dalam himpunan.
Pertanyaan dan Jawaban
T: Apa yang dimaksud dengan Bloom filter?
J: Bloom filter adalah struktur data yang memungkinkan komputer untuk melihat apakah elemen yang diberikan muncul dalam suatu set. Ia menggunakan fungsi hash untuk melakukan ini dengan menghitung nilai hash dari setiap elemen yang ditambahkan dan membandingkannya dengan elemen lain dalam set.
T: Apa jenis struktur data yang dimaksud dengan Bloom filter?
J: Bloom filter adalah struktur data probabilistik, yang berarti ada kemungkinan mendapatkan positif palsu tetapi tidak negatif palsu.
T: Siapa yang mengusulkan filter Bloom?
J: Edward Bloom mengusulkan filter Bloom pada tahun 1970.
T: Apa contoh Edward untuk menggunakan tekniknya?
J: Contoh Edward adalah menghubung-hubungkan sekitar 500.000 kata; dia menemukan bahwa dengan menggunakan tekniknya, dia bisa mengeliminasi sebagian besar pencarian dan mengurangi akses disk sebesar 15%.
T: Berapa banyak bit per elemen yang diperlukan untuk 1% probabilitas positif palsu?
J: Kurang dari 10 bit per elemen diperlukan untuk probabilitas positif palsu 1%, tidak tergantung pada ukuran atau jumlah elemen dalam himpunan.
T: Apakah mungkin untuk menghapus elemen dari filter bloom setelah ditambahkan?
J: Tidak, elemen hanya dapat ditambahkan ke himpunan tetapi tidak dapat dihapus.
T: Apakah menambahkan lebih banyak elemen meningkatkan atau menurunkan kemungkinan mendapatkan hasil positif palsu?
J: Menambahkan lebih banyak elemen meningkatkan kemungkinan mendapatkan hasil positif palsu.
