Adversary Resilient Learned Bloom Filters

• URL: http://arxiv.org/abs/2409.06556v4
• Date: Thu, 09 Jan 2025 14:56:37 GMT
• Title: Adversary Resilient Learned Bloom Filters
• Authors: Allison Bishop, Hayder Tirmazi,
• Abstract summary: 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.
• Score: 0.4910937238451484
• License:
• Abstract: The Learned Bloom Filter is a recently proposed data structure that combines the Bloom Filter with a Learning Model while preserving the Bloom Filter's one-sided error guarantees. Creating an adversary-resilient construction of the Learned Bloom Filter with provable guarantees is an open problem. We define a strong adversarial model for the Learned Bloom Filter. Our adversarial model extends an existing adversarial model designed for the Classical (i.e. not "Learned") Bloom Filter by prior work and considers computationally bounded adversaries that run in probabilistic polynomial time (PPT). Using our model, we construct an adversary-resilient variant of the Learned Bloom Filter called the Downtown Bodega Filter. We show that: if pseudo-random permutations exist, then an Adversary Resilient Learned Bloom Filter may be constructed with $2\lambda$ extra bits of memory and at most one extra pseudo-random permutation in the critical path. We construct a hybrid adversarial model for the case where a fraction of the query workload is chosen by an adversary. We show realistic scenarios where using the Downtown Bodega Filter gives better performance guarantees compared to alternative approaches in this hybrid model.

Related papers

• Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection [12.555117983678624]
  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.
  arXiv  Detail & Related papers  (2025-02-06T01:05:41Z)
• DPBloomfilter: Securing Bloom Filters with Differential Privacy [17.002793355495136]
  The DPBloomfilter integrates the classical differential privacy mechanism, specifically the Random Response technique, into the Bloom filter. It offers robust privacy guarantees under the same running complexity as the standard Bloom filter. This is the first work to provide differential privacy guarantees for the Bloom filter for membership query problems.
  arXiv  Detail & Related papers  (2025-02-02T06:47:50Z)
• 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)
• 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)
• 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)
• 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)
• Adversarial Robustness by Design through Analog Computing and Synthetic Gradients [80.60080084042666]
  We propose a new defense mechanism against adversarial attacks inspired by an optical co-processor. In the white-box setting, our defense works by obfuscating the parameters of the random projection. We find the combination of a random projection and binarization in the optical system also improves robustness against various types of black-box attacks.
  arXiv  Detail & Related papers  (2021-01-06T16:15:29Z)
• Training Interpretable Convolutional Neural Networks by Differentiating Class-specific Filters [64.46270549587004]
  Convolutional neural networks (CNNs) have been successfully used in a range of tasks. CNNs are often viewed as "black-box" and lack of interpretability. We propose a novel strategy to train interpretable CNNs by encouraging class-specific filters.
  arXiv  Detail & Related papers  (2020-07-16T09:12:26Z)
• Selective Inference for Latent Block Models [50.83356836818667]
  This study provides a selective inference method for latent block models. We construct a statistical test on a set of row and column cluster memberships of a latent block model. The proposed exact and approximated tests work effectively, compared to the naive test that did not take the selective bias into account.
  arXiv  Detail & Related papers  (2020-05-27T10:44:19Z)

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.