Bloom filters and their variants are widely used as space-efficient probabilistic data structures for representing sets and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications, a common engineering solution is to set the false positive rate very small and ignore the existence of the very unlikely false positive answers. This article is devoted to close the gap between the two design concepts ofunlikelyandnot havingfalse positives. We propose a data structure called EGH filter that supports the Bloom filter operations, and besides, it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false-positive free zone of a filter. We then generalize the filter to support the listing of the elements through the use of counters rather than bits. We detail networking applications of the filter and discuss potential generalizations. We evaluate the performance of the filter in comparison with the traditional Bloom filters. We also evaluate the price in terms of memory that needs to be paid to guarantee real false positive-free operations for having a deterministic Bloom filter-like behavior. Our data structure is based on recently developed combinatorial group testing techniques.

Bloom filters and their variants are widely used as space efficient probabilistic data structures for representing set systems and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications a common engineering solution is to set the false positive rate very small, and ignore the existence of the very unlikely false positive answers. This paper is devoted to close the gap between the two design concepts of unlikely and not having false positives. We propose a data structure, called EGH filter, that supports the Bloom filter operations and besides it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false positive free zone of a filter and generalize the filter to support listing of the elements. We evaluate the performance of the filter in comparison with the traditional Bloom filters. Our data structure is based on recently developed combinatorial group testing techniques.

Let ${\mathbb Z}^{+}$ be the set of positive integers. Let $C_{k}$ denote all subsets of ${\mathbb Z}^{+}$ such that none of them contains $k + 1$ pairwise coprime integers and $C_k(n)=C_k\cap \{1,2,\ldots,n\}$. Let $f(n, k) = \text{max}_{A \in C_{k}(n)}|A|$, where $|A|$ denotes the number of elements of the set $A$. Let $E_k(n)$ be the set of positive integers not exceeding $n$ which are divisible by at least one of the primes $p_{1}, \dots{}, p_{k}$, where $p_{i}$ denotes the $i$th prime number. In 1962, Erdös conjectured that $f(n, k) = |E(n,k)|$ for every $n \ge p_{k}$. Recently Chen and Zhou proved some results about this conjecture. In this paper we solve an open problem of Chen and Zhou and prove several related results about the conjecture.