Bloom filters for stream windows

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. In many systems, it becomes relevant to identify the more recent information in the data stream. However, the majority of the sliding window schemes consider the most recent elements of a data stream without taking into account time as a factor. While this allows, e.g., saving the most recent 10000 elements, it does not easily translate into storing data received in the last 60 seconds, unless the insertion rate is stable and known in advance. In this thesis, a new technique is explored, Unproved in terms of time complexity and memory usage compared to the already existing ones, 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. This new solution can be employed in a wide range of real world applications, such as in advertising, networking, fraud detection and distributed denial of service attacks prevention.

Um Bloom Filter é uma estrutura de dados probabilistica, cuja função é verificar, rapida-mente e eficientemente em termos de memória, se um elemento está presente no set. Tem sido vastamente utilizado em diversas áreas da informática e várias variantes, que permitem remoções, seis dinâmicos e funcionam com sliding windows, têm surgido ao longo dos anos. Em inúmeros sistemas, toma-se relevante identificar a informação mais recente do fluxo de dados. Contudo, a maioria dos esquemas em sliding windows considera os elementos mais recentes de um fluxo de dados sem ter em conta o tempo como um fator. Enquanto que isto permite, e.g., guardar os 10000 elementos mais recentes, não se traduz facilmente em armazenar dados recebidos nos últimos 60 segundos, a menos que a taxa de inserção seja estável e conhecida antecipadamente. Nesta dissertação, uma nova técnica é explorada, melhorada em termos de complexidade temporal e uso de memória comparativamente a outras já existentes, que consegue guardar informação de um dado período de tempo e identificá-la corretamente como presente quando uma consulta é feita, como também é capaz de eliminar dados quando estes "envelhecem". Esta nova solução pode ser utilizada numa vasta gama de aplicações do mundo real, tais como em publicidade, networking, deteção de fraude e prevenção de ataques distribuídos de negação de serviço.