Bloom filter variants for multiple sets: a comparative assessment

dc.contributor.authorCalderoni, Luca
dc.contributor.authorMaio, Dario
dc.contributor.authorPalmieri, Paolo
dc.date.accessioned2022-03-01T10:50:17Z
dc.date.available2022-03-01T10:50:17Z
dc.date.issued2022-02-28
dc.date.updated2022-02-28T17:17:43Z
dc.description.abstractIn this paper we compare two probabilistic data structures for association queries derived from the well-known Bloom filter: the shifting Bloom filter (ShBF), and the spatial Bloom filter (SBF). With respect to the original data structure, both variants add the ability to store multiple subsets in the same filter, using different strategies. We analyse the performance of the two data structures with respect to false positive probability, and the inter-set error probability (the probability for an element in the set of being recognised as belonging to the wrong subset). As part of our analysis, we extended the functionality of the shifting Bloom filter, optimising the filter for any non-trivial number of subsets. We propose a new generalised ShBF definition with applications outside of our specific domain, and present new probability formulas. Results of the comparison show that the ShBF provides better space efficiency, but at a significantly higher computational cost than the SBF.en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationCalderoni, L., Maio, D. and Palmieri, P. (2022) 'Bloom filter variants for multiple sets: a comparative assessment', Journal of Universal Computer Science, 28(2), pp. 120-140. doi: 10.3897/jucs.74230en
dc.identifier.doi10.3897/jucs.74230en
dc.identifier.endpage140en
dc.identifier.issn0948-695X
dc.identifier.issued2en
dc.identifier.journaltitleJournal of Universal Computer Scienceen
dc.identifier.startpage120en
dc.identifier.urihttps://hdl.handle.net/10468/12646
dc.identifier.volume28en
dc.language.isoenen
dc.publisherGraz University of Technology, Austriaen
dc.rights© 2022, the Authors. This is an open access article distributed under the Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0) license.en
dc.rights.urihttps://creativecommons.org/licenses/by-nd/4.0/en
dc.subjectProbabilistic data structuresen
dc.subjectSpatial bloom filteren
dc.subjectShifting bloom filteren
dc.subjectAssociation queriesen
dc.titleBloom filter variants for multiple sets: a comparative assessmenten
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Calderoni_Maio_Palmieri_JUCS2022.pdf
Size:
430.47 KB
Format:
Adobe Portable Document Format
Description:
Published Version
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description: