Penerapan Bloom Filter Pada Cache Dengan Tingkat False Positive Yang Rendah
View/ Open
Date
2016Author
Hidayat, Andri
Bukhari, Fahren
Sukoco, Heru
Metadata
Show full item recordAbstract
Objek/data merupakan bagian penting dalam suatu penyimpanan database.
Objek/data adalah data secara umum yaitu dapat berupa dokumen, file, maupun
gambar yang tersimpan didalam database. Setiap objek akan disimpan
menggunakan alamat tertentu dalam ruang penyimpanan. Untuk mendapatkan
suatu objek di dalam ruang penyimpanan memerlukan teknik pencarian yang baik
sehingga objek yang dicari dapat ditemukan.
Pencarian suatu objek pada umumnya memerlukan kecepatan dan
keakuratan terhadap objek yang ditemukan. Teknik pencarian berkaitan dengan
pengecekan membership suatu objek dalam suatu set. Pencarian suatu objek,
sederhananya dilakukan dengan mengecek satu per satu dari objek yang ada
sampai objek tersebut ditemukan. Pencarian dengan cara seperti ini mempunyai
akurasi yang tinggi tetapi memerlukan waktu yang lama untuk mendapatkan suatu
objek terutama pada suatu set yang sangat besar.
Penerapan teknik Bloom filter untuk mendapatkan objek pada suatu set data
yang besar merupakan hal yang tepat. Walaupun dalam penerapannya teknik
Bloom filter ini akan mengakibatkan adanya false positive, namun penggunaan
teknik ini lebih baik jika diterapkan pada suatu set dengan objek yang sangat
besar. False positive yang dihasilkan dari teknik Bloom filter bisa diminimalisir
dengan memvariasikan variabel-variabel yang dapat mempengaruhinya. Beberapa
variabel yang berpengaruh pada false positive adalah jumlah objek, jumlah bit
yang disediakan, dan jumlah pemetaan objek (map bit).
Penelitian ini menguji keakuratan algoritme Bloom filter menggunakan
algoritme sequential search untuk mendapatkan membership suatu objek pada
suatu set yang besar yang di-cache. Selain itu untuk mendapatkan kombinasi yang
tepat dari parameter-parameter yang bisa mempengaruhi adanya false positive
pada Bloom filter sehingga mendapatkan tingkat false positive yang rendah.
Metode dalam penelitian ini diawali dengan merancang model Bloom filter
dan sequential search, kemudian dilanjutkan dengan membuat simulasi untuk
kedua model yang ada. Simulasi dengan membuat sekenario bahwa terdapat satu
set objek dengan jumlah yang sangat besar. Kemudian ditetapkan sebagian kecil
objek yang akan disimpan pada buffer. Tahapan dilanjutkan dengan memilih satu
objek yang ada pada set secara acak untuk selanjutnya dibandingkan dengan objek
pada buffer menggunakan Bloom filter dan menggunakan sequential search.
Berikutnya yaitu tahapan menghitung false positive dan false negative serta
menghitung perbedaan waktu antara hasil pencarian menggunakan Bloom filter
dan sequential search. Tahapan selanjutnya setelah tahapan simulasi secara
keseluruhan adalah analisis terhadap hasil, evaluasi, dan penarikan kesimpulan.
Dalam penelitian ini didapatkan hasil bahwa kecepatan pencarian
membership suatu objek pada set yang sangat besar menggunakan metode Bloom
filter lebih cepat yaitu rata-rata 10μs dan cenderung lebih stabil bahkan lebih
cepat (0μs) dari pencarian menggunakan sequential search yang memerlukan
waktu hingga 420μs untuk pencarian dengan jumlah objek yang sama. False
iv
positive terendah dihasilkan oleh kombinasi parameter jumlah objek= 2000000
jumlah bit = 8, dan map bit = 7 dengan objek yang ada pada buffer sebesar 6%.