Autoscaling Bloom Filter: Controlling Trade-off Between True and False Positives

Abstract

A Bloom filter is a simple data structure supporting membership queries on a set. The standard Bloom filter does not support the delete operation, therefore, many applications use a counting Bloom filter to enable deletion. This paper proposes a generalization of the counting Bloom filter approach, called "autoscaling Bloom filters", which allows adjustment of its capacity with probabilistic bounds on false positives and true positives. In essence, the autoscaling Bloom filter is a binarized counting Bloom filter with an adjustable binarization threshold. We present the mathematical analysis of the performance as well as give a procedure for minimization of the false positive rate.

arXiv comment13 pages, 3 figures

Cited by in corpus (10)

• A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part II: Applications, Cognitive Models, and Challenges
• A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
• A comparison of Vector Symbolic Architectures
• HyperEmbed: Tradeoffs Between Resources and Performance in NLP Tasks with Hyperdimensional Computing enabled Embedding of n-gram Statistics
• Perceptron Theory Can Predict the Accuracy of Neural Networks
• Efficient Decoding of Compositional Structure in Holistic Representations
• On Effects of Compression with Hyperdimensional Computing in Distributed Randomized Neural Networks
• Integer Factorization with Compositional Distributed Representations
• Generalized Learning Vector Quantization for Classification in Randomized Neural Networks and Hyperdimensional Computing
• Hyperdimensional Computing for Efficient Distributed Classification with Randomized Neural Networks