Sidang Tugas Akhir

Adi Riswanto
g54100062

Pemeriksaan Keanggotaan Elemen pada Himpunan dengan Bloom Filter

Suatu himpunan adalah kumpulan dari objek-objek atau item-item yang dapat didefinisikan dengan sangat jelas. Cara menyimpan atau merepresentasikan data agar bisa dipakai secara efisien disebut dengan struktur data. Di dalam struktur data terdapat operasi penambahan anggota ke dalam himpunan maupun pengujian keanggotaan dalam himpunan tersebut. Bagi beberapa aplikasi, pencocokan secara cepat dalam pengujian keanggotaan tentu merupakan suatu kebutuhan. Suatu himpunan dapat memiliki elemen yang banyak sehingga mengembangkan solusi untuk menyimpan, memperbarui, dan mengolahnya menjadi semakin penting. Beberapa struktur data seperti pohon pencarian biner dan tries ditawarkan menjadi solusi. Namun struktur data tersebut memerlukan waktu yang cukup lama untuk menambahkan elemen maupun untuk memeriksa apakah suatu elemen berada dalam himpunannya atau tidak (Guo et al 2010). Solusi lain yang ditawarkan untuk menangani masalah waktu penambahan elemen dan pengujian elemen dalam himpunan adalah dengan algoritma Bloom Filter. Bloom Filter adalah sebuah ruang efisien probabilistik data, yang dikemukakan oleh Burton Howard Bloom pada tahun 1970 yang digunakan untuk menguji apakah suatu elemen berada di dalam himpunan atau tidak. Bloom Filter memanfaatkan teknik hashing untuk membuat setiap elemen menjadi unik. Meski memiliki banyak kelebihan, dalam Bloom Filter terdapat suatu kelemahan yaitu terjadinya tabrakan hash (collision) yang dapat menyebabkan kesalahan dalam hasil pengujian. Dalam beberapa aplikasi hal ini dianggap tidak terlalu berbahaya. Pada karya ilmiah ini akan dibahas mengenai algoritma dari Bloom Filter, masalah munculnya elemen false positive pada hasil pengujian, perhitungan peluang false positive, dan cara untuk mengoptimalkan elemen false positive tersebut.