Algorithms with Predictions: I vantaggi di un approccio ibrido nel caso studio dei Bloom filter

This thesis integrates MLP and GRU models into Bloom filters to overcome worst-case analysis limits by exploiting specific data patterns. The Python implementation utilizes bitarray, MurmurHash3, and PyTorch to evaluate the structure's efficiency and predictive capability. The primary focus is reducing the false positive rate under a strict total memory budget that accounts for the model's footprint. This approach quantifies the effectiveness of learned filters against traditional solutions in real-world application scenarios. Finally, it analyzes the critical trade-off between neural parameter overhead and the space saved in the backup filter.

La tesi integra modelli MLP e GRU nei filtri di Bloom per superare i limiti della worst-case analysis sfruttando i pattern specifici dei dati. L’implementazione in Python impiega bitarray, MurmurHash3 e PyTorch per valutare l'efficienza e la capacità predittiva della struttura. Il focus principale è la riduzione del false positive rate operando a parità di budget di memoria totale, includendo il peso del modello nel calcolo. Questo approccio permette di quantificare l'efficacia dei learned filters rispetto alle soluzioni tradizionali in scenari applicativi reali. Si analizza così il trade-off critico tra l'ingombro dei parametri neurali e il risparmio di spazio nel filtro di backup.