Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m, n, t) (resp. s_N(m, n, t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m, n, t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2, t ≥ ⌊log n⌋+1. In this work, we improve this bound when the probes are allowed to be superlinear in n, i. e. , when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m, n, t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m, n, t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m, n, 3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i. e. , s_N(m, 2, 3) ≥ Ω(√m).

Authors

• Palash Dey
• Jaikumar Radhakrishnan
• Santhoshini Velusamy

Keywords

• Set membership
• Bit-probe model
• Fully-explicit data structures
• Adaptive data structures
• Error-correcting codes