Time-limited Bloom Filter

• Type: Article in International Conference Proceedings Book
• Date: 2023

Authors

Rodrigues, A (Author) Other; Shtul, A (Author) Other; Baquero, C (Author) FEUP; Almeida, PS (Author) Other

Conference proceedings International

Title: Proceedings of the ACM Symposium on Applied Computing

Pages: 1285-1288

38th Annual ACM Symposium on Applied Computing, SAC 2023

27 March 2023 through 31 March 2023

Indexing

ISI Web of Knowledge - 0 Citations

Scopus

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 4