Time-limited Bloom Filter

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2023

Autores

Rodrigues, A (Autor) Outra; Shtul, A (Autor) Outra; Baquero, C (Autor) FEUP; Almeida, PS (Autor) Outra

Ata de Conferência Internacional

Título: Proceedings of the ACM Symposium on Applied Computing

Páginas: 1285-1288

38th Annual ACM Symposium on Applied Computing, SAC 2023

27 March 2023 through 31 March 2023

Indexação

ISI Web of Knowledge - 0 Citações

Scopus

Outras Informações

ID Authenticus: P-00Y-HGW

DOI: 10.1145/3555776.3577791

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 4