Adaptive one memory access bloom filters

e-Archivo Repository

Show simple item record Reviriego Vasallo, Pedro Sánchez-Macián, Alfonso Rottenstreich, Ori Larrabeiti López, David 2022-06-22T11:19:43Z 2022-06-22T11:19:43Z 2022-06
dc.identifier.bibliographicCitation Reviriego, P., et al. IEEE Transactions on Network and Service Management, 19(2), June 2022, Pp. 848-859
dc.identifier.issn 1932-4537
dc.description.abstract Bloom 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.
dc.description.sponsorship This 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.
dc.format.extent 12
dc.language.iso eng
dc.publisher IEEE
dc.rights © 2022 IEEE.
dc.subject.other Computer networks
dc.subject.other Data structures
dc.subject.other Bloom filter
dc.title Adaptive one memory access bloom filters
dc.type article
dc.subject.eciencia Telecomunicaciones
dc.rights.accessRights openAccess
dc.relation.projectID Gobierno de España. PID2019-104207RB-I00
dc.relation.projectID Gobierno de España. RED2018-102585-T
dc.relation.projectID Comunidad de Madrid. P2018/TCS-4496
dc.type.version acceptedVersion
dc.identifier.publicationfirstpage 848
dc.identifier.publicationissue 2
dc.identifier.publicationlastpage 859
dc.identifier.publicationtitle IEEE Transactions on Network and Service Management
dc.identifier.publicationvolume 19
dc.identifier.uxxi AR/0000029190
dc.contributor.funder Comunidad de Madrid
dc.contributor.funder Agencia Estatal de Investigación (España)
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)

This item appears in the following Collection(s)

Show simple item record