Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/90004
Registo completo
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.author | Almeida, Paulo Sérgio | por |
dc.date.accessioned | 2024-03-25T19:27:28Z | - |
dc.date.available | 2024-03-25T19:27:28Z | - |
dc.date.issued | 2023 | - |
dc.identifier.citation | Almeida, P. S. (2023). A Case for Partitioned Bloom Filters. IEEE Transactions on Computers. Institute of Electrical and Electronics Engineers (IEEE). http://doi.org/10.1109/tc.2022.3218995 | por |
dc.identifier.issn | 0018-9340 | - |
dc.identifier.uri | https://hdl.handle.net/1822/90004 | - |
dc.description.abstract | In a partitioned Bloom Filter (PBF) the bit vector is split into disjoint parts, one per hash function. Contrary to hardware designs, where they prevail, software implementations mostly ignore PBFs, considering them worse than standard Bloom filters (SBF), due to the slightly larger false positive rate (FPR). In this paper, by performing an in-depth analysis, first we show that the FPR advantage of SBFs is smaller than thought; more importantly, by deriving the per-element FPR, we show that SBFs have weak spots in the domain: elements that test as false positives much more frequently than expected. This is relevant in scenarios where an element is tested against many filters. Moreover, SBFs are prone to exhibit extremely weak spots if naive double hashing is used, something occurring in mainstream libraries. PBFs exhibit a uniform distribution of the FPR over the domain, with no weak spots, even using naive double hashing. Finally, we survey scenarios beyond set membership testing, identifying many advantages of having disjoint parts, in designs using SIMD techniques, for filter size reduction, test of set disjointness, and duplicate detection in streams. PBFs are better, and should replace SBFs, in general purpose libraries and as the base for novel designs. | por |
dc.description.sponsorship | - (undefined) | por |
dc.language.iso | eng | por |
dc.publisher | IEEE | por |
dc.rights | openAccess | por |
dc.subject | Information filtering | por |
dc.subject | partitioned bloom filters | por |
dc.subject | probabilistic data structures | por |
dc.title | A case for partitioned Bloom Filters | por |
dc.type | article | por |
dc.peerreviewed | yes | por |
dc.relation.publisherversion | https://ieeexplore.ieee.org/document/9935317 | por |
oaire.citationStartPage | 1681 | por |
oaire.citationEndPage | 1691 | por |
oaire.citationIssue | 6 | por |
oaire.citationVolume | 72 | por |
dc.date.updated | 2024-03-21T11:43:53Z | - |
dc.identifier.doi | 10.1109/TC.2022.3218995 | por |
dc.subject.fos | Engenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informática | por |
sdum.export.identifier | 13599 | - |
sdum.journal | IEEE Transactions on Computers | por |
oaire.version | AM | por |
Aparece nas coleções: | HASLab - Artigos em revistas internacionais |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
TC3218995-accepted-version.pdf | 630,24 kB | Adobe PDF | Ver/Abrir |