The study by Paulo Sérgio Almeida, INESC TEC researcher and professor at the University of Minho, focuses on Bloom Filters, a very popular probabilistic data structure in the design of databases, distributed systems, and communication networks. The study, which demonstrates the versatility of partitioned Bloom Filters, was accepted for publication in IEEE Transactions on Computers, one of the top journals in Informatics and Computing.
“The study aims to demystify the widespread idea that partitioned Bloom Filters perform worse than standard Bloom Filters, just because they feature a very slight advantage in the false positive rate – when, in fact, they are much less versatile in general”, explained Paulo Sérgio Almeida.
With this study, the researcher advances a set of advantages in the use of partitioned filters, highlighting their versatility – namely, as a starting point for the development of new data structures. “An example of this are the Age-Partitioned Bloom Filters, which can be used to test for the presence of elements in a sliding window, in stream processing”, he added.
From this analysis, the researcher contributes to deepen the knowledge about this data structure, presenting a series of particularly useful conclusions for those who need to choose a data structure to represent sets in an approximate and compact way, as well as for those who develop new data structures inspired by Bloom Filters.
“This paper has an impact on application developers dedicated to many areas, i.e., databases, distributed systems, computer communications. As representations of sets is something very generic, advancing the state-of-the-art in this field is useful in general”, concluded the researcher.
The results of this study are available in the paper “A Case for Partitioned Bloom Filters”, which was accepted and published in the international journal IEEE Transactions on Computers, classified as Q1 by Scopus, a top reference in the area.
The INESC TEC researcher mentioned in this news piece is associated with INESC TEC and UMinho.
News, current topics, curiosities and so much more about INESC TEC and its community!
