Performance Evaluation of Bloom Multifilters

Show full item record

Title: Performance Evaluation of Bloom Multifilters
Author: Concas, Francesco
Other contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos
University of Helsinki, Faculty of Science, Department of Computer Science
Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap
Publisher: Helsingin yliopisto
Date: 2018
Language: eng
Thesis level: master's thesis
Discipline: Computer science
Abstract: The Bloom Filter is a space-efficient probabilistic data structure that deals with the problem of set membership. The space reduction comes at the expense of introducing a false positive rate that many applications can tolerate since they require approximate answers. In this thesis, we extend the Bloom Filter to deal with the problem of matching multiple labels to a set, introducing two new data structures: the Bloom Vector and the Bloom Matrix. We also introduce a more efficient variation for each of them, namely the Optimised Bloom Vector and the Sparse Bloom Matrix. We implement them and show experimental results from testing with artificial datasets and a real dataset.

Files in this item

Total number of downloads: Loading...

Files Size Format View
Performance_Evaluation_of_Bloom_Multifilters.pdf 714.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record