Performance Evaluation of Bloom Multifilters

Show full item record



Permalink

http://urn.fi/URN:NBN:fi:hulib-201804131683
Title: Performance Evaluation of Bloom Multifilters
Author: Concas, Francesco
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Publisher: Helsingin yliopisto
Date: 2018
Language: eng
URI: http://urn.fi/URN:NBN:fi:hulib-201804131683
http://hdl.handle.net/10138/234248
Thesis level: master's thesis
Discipline: Computer science
Tietojenkäsittelytiede
Datavetenskap
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