Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

 
Data Skripsi
 
Judul : Pemeriksaan Keanggotaan Elemen pada Himpunan dengan Bloom Filter
Jenis : Skripsi
Penulis : Adi Riswanto
NRP : g54100062
Tanggal Lulus : 27 January 2015
Tanggal Seminar : 26 November 2014 09:00
Tanggal Sidang : 09 December 2014 11:00
Pembimbing : Dr. Ir. Fahren Bukhari, M.Sc.
Elis Khatizah, S.Si., M.Si.

Ringkasan : 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.

Random Quotes

Memberikan seluruh cintamu kepada seseorang bukanlah jaminan dia akan membalas cintamu. Jangan mengharapkan balasan cinta, tunggulah sampai cinta berkembang di hatinya, tetapi jika tidak, berbahagialah karena cinta tumbuh di hatimu.

anonim