Non-adaptive set membership schemes improved by removing extra logarithmic factor
Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
Data Structures and Algorithms
Summary
Checking if an item belongs in a set can be done efficiently by reading only a few bits from a data structure. The authors revisited a previous method that used random graphs and discovered a way to simplify the math by ensuring a stronger connection property. This led to a clearer calculation that removes an extra multiplying factor in the scheme’s size for cases reading five or more bits. This means certain data structures for set membership can be made slightly smaller without sacrificing reliability.
What this means in practice
- •For database engineers: Design smaller static data indexes that quickly check membership with fixed bit reads, improving storage efficiency.
- •For network protocol designers: Implement concise membership tests in networking hardware where queries must be answered by reading few bits non-adaptively.
A theory result. No direct application yet.
Authors
Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw, Vikash Tripathi
Abstract
We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed $t\ge5$, a logarithm-free existence bound of $O_t(m^{1/c}n^{1-1/c})$, where $c=\lfloor(t-1)/2\rfloor$. For odd $t$, this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].