License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.28
URN: urn:nbn:de:0030-drops-126965
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12696/
Dey, Palash ;
Radhakrishnan, Jaikumar ;
Velusamy, Santhoshini
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
Abstract
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).
BibTeX - Entry
@InProceedings{dey_et_al:LIPIcs:2020:12696,
author = {Palash Dey and Jaikumar Radhakrishnan and Santhoshini Velusamy},
title = {{Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {28:1--28:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12696},
URN = {urn:nbn:de:0030-drops-126965},
doi = {10.4230/LIPIcs.MFCS.2020.28},
annote = {Keywords: Set membership, Bit-probe model, Fully-explicit data structures, Adaptive data structures, Error-correcting codes}
}
|
Keywords: |
|
Set membership, Bit-probe model, Fully-explicit data structures, Adaptive data structures, Error-correcting codes |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
