Succinct Filters for Sets of Unknown Sizes
Preprint
Abstract
The membership problem asks to maintain a set $S\subseteq[u]$, supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that computes exact answers is called a dictionary. When a (small) false positive rate $\epsilon$ is allowed, the data structure is called a filter. The space usages of the standard dictionaries or filters usually depend on the upper bound on the size of $S$, while the actual set can be much smaller. Pagh, Segev and Wieder (FOCS'13) were the first to study filters with varying space usage based on the current $|S|$. They showed in order to match the space with the current set size $n=|S|$, any filter data structure must use $(1-o(1))n(\log(1/\epsilon)+(1-O(\epsilon))\log\log n)$ bits, in contrast to the well-known lower bound of $N\log(1/\epsilon)$ bits, where $N$ is an upper bound on $|S|$. They also presented a data structure with almost optimal space of $(1+o(1))n(\log(1/\epsilon)+O(\log\log n))$ bits provided that $n>u^{0.001}$, with expected amortized constant insertion time and worst-case constant lookup time. In this work, we present a filter data structure with improvements in two aspects: - it has constant worst-case time for all insertions and lookups with high probability; - it uses space $(1+o(1))n(\log (1/\epsilon)+\log\log n)$ bits when $n>u^{0.001}$, achieving optimal leading constant for all $\epsilon=o(1)$. We also present a dictionary that uses $(1+o(1))n\log(u/n)$ bits of space, matching the optimal space in terms of the current size, and performs all operations in constant time with high probability.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- An improved algorithm based on Bloom filter and its application in bar code recognition and processingEURASIP Journal on Image and Video Processing, 2018
- Par-BF: A parallel partitioned Bloom filter for dynamic data setsThe International Journal of High Performance Computing Applications, 2016
- Bloom Filters in Adversarial Environments2015
- Algorithmic Nuggets in Content DeliveryACM SIGCOMM Computer Communication Review, 2015
- Derandomized Constructions of k-Wise (Almost) Independent PermutationsAlgorithmica, 2008
- Scalable Bloom FiltersInformation Processing Letters, 2007
- Hash-AV: fast virus signature scanning by cache-resident filters2005
- Chernoff–Hoeffding Bounds for Applications with Limited IndependenceSIAM Journal on Discrete Mathematics, 1995