Detalhes
Nome
Paulo Sérgio AlmeidaCargo
Investigador SéniorDesde
01 novembro 2011
Nacionalidade
PortugalCentro
Laboratório de Software ConfiávelContactos
+351253604440
paulo.s.almeida@inesctec.pt
2023
Autores
Barros, M; Ramos, M; Gomes, A; Cunha, A; Pereira, J; Almeida, PS;
Publicação
Formal Techniques for Distributed Objects, Components, and Systems - 43rd IFIP WG 6.1 International Conference, FORTE 2023, Held as Part of the 18th International Federated Conference on Distributed Computing Techniques, DisCoTec 2023, Lisbon, Portugal, June 19-23, 2023, Proceedings
Abstract
2023
Autores
Rodrigues, A; Shtul, A; Baquero, C; Almeida, PS;
Publicação
38TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING, SAC 2023
Abstract
A Bloom Filter is a probabilistic data structure designed to check, rapidly and memory-efficiently, whether an element is present in a set. It has been vastly used in various computing areas and several variants, allowing deletions, dynamic sets and working with sliding windows, have surfaced over the years. When summarizing data streams, it becomes relevant to identify the more recent elements in the stream. However, most of the sliding window schemes consider the most recent items of a data stream without considering time as a factor. While this allows, e.g., storing the most recent 10000 elements, it does not easily translate into storing elements received in the last 60 seconds, unless the insertion rate is stable and known in advance. In this paper, we present the Time-limited Bloom Filter, a new BF-based approach that can save information of a given time period and correctly identify it as present when queried, while also being able to retire data when it becomes stale. The approach supports variable insertion rates while striving to keep a target false positive rate. We also make available a reference implementation of the data structure as a Redis module.
2023
Autores
Almeida, PS;
Publicação
IEEE TRANSACTIONS ON COMPUTERS
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.
2023
Autores
Almeida, PS;
Publicação
CoRR
Abstract
2022
Autores
Weidner, M; Almeida, PS;
Publicação
PAPOC'22: PROCEEDINGS OF THE 9TH PRINCIPLES AND PRACTICE OF CONSISTENCY FOR DISTRIBUTED DATA
Abstract
Embedding CRDT counters has shown to be a challenging topic, since their introduction in Riak Maps. The desire for obliviousness, where all information about a counter is fully removed upon key removal, faces problems due to the possibility of concurrency between increments and key removals. Previous state-based proposals exhibit undesirable reset-wins semantics, which lead to losing increments, unsatisfactorily solved through manual generation management in the API. Previous operation-based approaches depend on causal stability, being prone to unbounded counter growth under network partitions. We introduce a novel embeddable operation-based CRDT counter which achieves both desirable observed-reset semantics and obliviousness upon resets. Moreover, it achieves this while merely requiring FIFO delivery, allowing a tradeoff between causal consistency and faster information propagation, being more robust under network partitions.
Teses supervisionadas
2022
Autor
Liz Lopes Almeida Gomes
Instituição
UP-FEUP
2020
Autor
Diogo Peixoto Pereira
Instituição
UP-FEUP
2020
Autor
Francisco Tuna de Andrade
Instituição
UP-FEUP
2020
Autor
Bruno Gomes
Instituição
IPP-ISEP
2019
Autor
Nuno Miguel Santos Marques
Instituição
UP-FCUP
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.