Publication:
Adaptive one memory access bloom filters

dc.affiliation.dptoUC3M. Departamento de Ingeniería Telemáticaes
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Network Technologieses
dc.contributor.authorReviriego Vasallo, Pedro
dc.contributor.authorSánchez-Macián, Alfonso
dc.contributor.authorRottenstreich, Ori
dc.contributor.authorLarrabeiti López, David
dc.contributor.funderComunidad de Madrides
dc.contributor.funderAgencia Estatal de Investigación (España)es
dc.date.accessioned2022-06-22T11:19:43Z
dc.date.available2022-06-22T11:19:43Z
dc.date.issued2022-06
dc.description.abstractBloom filters are widely used to perform fast approximate membership checking in networking applications. The main limitation of Bloom filters is that they suffer from false positives that can only be reduced by using more memory. We suggest to take advantage of a common repetition in the identity of queried elements to adapt Bloom filters for avoiding false positives for elements that repeat upon queries. In this paper, one memory access Bloom filters are used to design an adaptation scheme that can effectively remove false positives while completing all queries in a single memory access. The proposed filters are well suited for scenarios on which the number of memory bits per element is low and thus complement existing adaptive cuckoo filters that are not efficient in that case. The evaluation results using packet traces show that the proposed adaptive Bloom filters can significantly reduce the false positive rate in networking applications with the single memory access. In particular, when using as few as four bits per element, false positive rates below 5% are achieved.en
dc.description.sponsorshipThis work was supported by the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Agencia Estatal de Investigación (AEI) 10.13039/501100011033 and by the Madrid Community research project TAPIR-CM grant no. P2018/TCS-4496.en
dc.format.extent12es
dc.identifier.bibliographicCitationReviriego, P., et al. IEEE Transactions on Network and Service Management, 19(2), June 2022, Pp. 848-859en
dc.identifier.doihttps://doi.org/10.1109/TNSM.2022.3145436
dc.identifier.issn1932-4537
dc.identifier.publicationfirstpage848es
dc.identifier.publicationissue2es
dc.identifier.publicationlastpage859es
dc.identifier.publicationtitleIEEE Transactions on Network and Service Managementen
dc.identifier.publicationvolume19es
dc.identifier.urihttps://hdl.handle.net/10016/35229
dc.identifier.uxxiAR/0000029190
dc.language.isoengen
dc.publisherIEEEen
dc.relation.projectIDGobierno de España. PID2019-104207RB-I00es
dc.relation.projectIDGobierno de España. RED2018-102585-Tes
dc.relation.projectIDComunidad de Madrid. P2018/TCS-4496es
dc.rights© 2022 IEEE.en
dc.rights.accessRightsopen accessen
dc.subject.ecienciaTelecomunicacioneses
dc.subject.otherComputer networksen
dc.subject.otherData structuresen
dc.subject.otherBloom filteren
dc.titleAdaptive one memory access bloom filtersen
dc.typeresearch article*
dc.type.hasVersionAM*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
adaptive_TNSM_2022_ps.pdf
Size:
1.59 MB
Format:
Adobe Portable Document Format