Studio e analisi prestazionale dei Cuckoo Filter come alternativa efficiente ai Bloom Filter

This study focuses on the analysis of Cuckoo Filters, a probabilistic data structure for set membership testing, proposed as an alternative to traditional Bloom Filters. The analysis is based on the paper "Cuckoo Filter: Practically Better Than Bloom Filter" by Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher, with the aim of exploring the theoretical principles and techniques used to achieve high efficiency in terms of memory usage and performance. Starting from the analysis of the existing literature, the functioning of Cuckoo Filters and the main supported operations, such as insertion, lookup, and deletion of elements, are examined. These operations are based on Cuckoo Hashing mechanisms and the use of fingerprints. The focus is placed on the characteristics of the data structure, the implementation choices, and the mechanisms that determine its behavior in terms of efficiency and memory utilization. The analysis highlights the characteristics of Cuckoo Filters, their strengths, and their limitations compared to Bloom Filters, providing an overall view of both the theoretical and implementation aspects of this data structure.

Lo studio affronta l'analisi dei Cuckoo Filter, una struttura dati probabilistica per il test di appartenenza ad un insieme, proposta come alternativa ai tradizionali Bloom Filter. L'analisi prende come riferimento il paper "Cuckoo Filter: Practically Better Than Bloom Filter" di Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, con l'obiettivo di approfondire i principi teorici e le tecniche utilizzate per ottenere un'elevata efficienza in termini di occupazione della memoria e prestazioni. A partire dall'analisi della letteratura, viene approfondito il funzionamento dei Cuckoo Filter e delle principali operazioni supportate, quali inserimento, ricerca ed eliminazione degli elementi, basate sui meccanismi di Cuckoo Hashing e sull'utilizzo delle fingerprint. L'attenzione è rivolta alle caratteristiche della struttura dati, alle scelte implementative ed ai meccanismi che ne determinano il comportamento in termini di efficienza ed utilizzo della memoria. L'analisi permette di evidenziare le caratteristiche dei Cuckoo Filter, i loro punti di forza e i limiti rispetto ai Bloom Filter, fornendo una visione complessiva degli aspetti teorici e implementativi della struttura dati.