Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection

• URL: http://arxiv.org/abs/2502.03696v1
• Date: Thu, 06 Feb 2025 01:05:41 GMT
• Title: Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
• Authors: Atsuki Sato, Yusuke Matsui,
• Abstract summary: We propose the Cascaded Learned Bloom Filter (CLBF) to address these issues. Our dynamic programming-based optimization automatically selects configurations that achieve an optimal balance between the model and filter sizes. Experiments on real-world datasets show that CLBF reduces memory usage by up to 24% and decreases reject time by up to 14 times compared to state-of-the-art learned Bloom filters.
• Score: 12.555117983678624
• License:
• Abstract: Recent studies have demonstrated that learned Bloom filters, which combine machine learning with the classical Bloom filter, can achieve superior memory efficiency. However, existing learned Bloom filters face two critical unresolved challenges: the balance between the machine learning model size and the Bloom filter size is not optimal, and the reject time cannot be minimized effectively. We propose the Cascaded Learned Bloom Filter (CLBF) to address these issues. Our dynamic programming-based optimization automatically selects configurations that achieve an optimal balance between the model and filter sizes while minimizing reject time. Experiments on real-world datasets show that CLBF reduces memory usage by up to 24% and decreases reject time by up to 14 times compared to state-of-the-art learned Bloom filters.

Related papers

• A Privacy Model for Classical & Learned Bloom Filters [0.0]
  The Classical Bloom Filter (CBF) is a class of Probabilistic Data Structures (PDS) The Learned Bloom Filter (LBF) is a recently proposed class of PDS that combines the Classical Bloom Filter with a Learning Model.
  arXiv  Detail & Related papers  (2025-01-27T03:35:25Z)
• Adversary Resilient Learned Bloom Filters [0.4910937238451484]
  We define a strong adversarial model for the Learned Bloom Filter. Using our model, we construct an adversary-resilient variant of the Learned Bloom Filter called Downtown Bodega Filter.
  arXiv  Detail & Related papers  (2024-09-10T14:37:43Z)
• Filter Pruning for Efficient CNNs via Knowledge-driven Differential Filter Sampler [103.97487121678276]
  Filter pruning simultaneously accelerates the computation and reduces the memory overhead of CNNs. We propose a novel Knowledge-driven Differential Filter Sampler(KDFS) with Masked Filter Modeling(MFM) framework for filter pruning.
  arXiv  Detail & Related papers  (2023-07-01T02:28:41Z)
• A Critical Analysis of Classifier Selection in Learned Bloom Filters [0.3359875577705538]
  "Complexity" of the data used to build the filter might heavily impact on its performance. We propose a novel methodology, supported by software, for designing, analyzing and implementing Learned Bloom Filters. Experiments show that the proposed methodology and the supporting software are valid and useful.
  arXiv  Detail & Related papers  (2022-11-28T17:17:18Z)
• Compressing (Multidimensional) Learned Bloom Filters [7.6058140480517356]
  A Bloom filter reveals if an element is not included in the underlying set or is included with a certain error rate. Deep learning models are used to solve this membership testing problem. We show that the benefits of learned Bloom filters are apparent only when considering a vast amount of data.
  arXiv  Detail & Related papers  (2022-08-05T07:54:48Z)
• Pruning Networks with Cross-Layer Ranking & k-Reciprocal Nearest Filters [151.2423480789271]
  A novel pruning method, termed CLR-RNF, is proposed for filter-level network pruning. We conduct image classification on CIFAR-10 and ImageNet to demonstrate the superiority of our CLR-RNF over the state-of-the-arts.
  arXiv  Detail & Related papers  (2022-02-15T04:53:24Z)
• Learning Versatile Convolution Filters for Efficient Visual Recognition [125.34595948003745]
  This paper introduces versatile filters to construct efficient convolutional neural networks. We conduct theoretical analysis on network complexity and an efficient convolution scheme is introduced. Experimental results on benchmark datasets and neural networks demonstrate that our versatile filters are able to achieve comparable accuracy as that of original filters.
  arXiv  Detail & Related papers  (2021-09-20T06:07:14Z)
• Training Compact CNNs for Image Classification using Dynamic-coded Filter Fusion [139.71852076031962]
  We present a novel filter pruning method, dubbed dynamic-coded filter fusion (DCFF) We derive compact CNNs in a computation-economical and regularization-free manner for efficient image classification. Our DCFF derives a compact VGGNet-16 with only 72.77M FLOPs and 1.06M parameters while reaching top-1 accuracy of 93.47%.
  arXiv  Detail & Related papers  (2021-07-14T18:07:38Z)
• Unsharp Mask Guided Filtering [53.14430987860308]
  The goal of this paper is guided image filtering, which emphasizes the importance of structure transfer during filtering. We propose a new and simplified formulation of the guided filter inspired by unsharp masking. Our formulation enjoys a filtering prior to a low-pass filter and enables explicit structure transfer by estimating a single coefficient.
  arXiv  Detail & Related papers  (2021-06-02T19:15:34Z)
• Data Agnostic Filter Gating for Efficient Deep Networks [72.4615632234314]
  Current filter pruning methods mainly leverage feature maps to generate important scores for filters and prune those with smaller scores. In this paper, we propose a data filter pruning method that uses an auxiliary network named Dagger module to induce pruning. In addition, to help prune filters with certain FLOPs constraints, we leverage an explicit FLOPs-aware regularization to directly promote pruning filters toward target FLOPs.
  arXiv  Detail & Related papers  (2020-10-28T15:26:40Z)
• Partitioned Learned Bloom Filter [31.748077944821315]
  We show how to frame the problem of optimal model utilization as an optimization problem. We derive algorithms that can achieve near-optimal performance in many cases.
  arXiv  Detail & Related papers  (2020-06-05T00:05:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.