On the Choice of General Purpose Classifiers in Learned Bloom Filters:\n An Initial Analysis Within Basic Filters

2021/12/13 by Giacomo Fumagalli, Davide Raimondi, Fumagalli, Giacomo +7
Computer Science · #68T07 #Caching and Content Delivery #FOS: Computer and information sciences #I.2.6 #Machine Learning (cs.LG) #Neural and Evolutionary Computing (cs.NE)

paper · pdf · doi:10.48550/arxiv.2112.06563

openalex publication_date 2021/12/13 · openalex created_date 2022/11/20 · openalex updated_date 2026/07/28

Abstract

Bloom Filters are a fundamental and pervasive data structure. Within the\ngrowing area of Learned Data Structures, several Learned versions of Bloom\nFilters have been considered, yielding advantages over classic Filters. Each of\nthem uses a classifier, which is the Learned part of the data structure.\nAlthough it has a central role in those new filters, and its space footprint as\nwell as classification time may affect the performance of the Learned Filter,\nno systematic study of which specific classifier to use in which circumstances\nis available. We report progress in this area here, providing also initial\nguidelines on which classifier to choose among five classic classification\nparadigms.\n

Related

• A Critical Analysis of Classifier Selection in Learned Bloom Filters
• A Model for Learned Bloom Filters and Related Structures
• Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier
• A Model for Learned Bloom Filters, and Optimizing by Sandwiching
• Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection