文章基本信息
- 标题：Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
- 本地全文：下载
- 作者：Palash Dey ; Jaikumar Radhakrishnan ; Santhoshini Velusamy 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：170
- 页码：28:1-28:12
- DOI：10.4230/LIPIcs.MFCS.2020.28
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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âOSlog nâO<, n-3/2})}) for n ⥠2,t ⥠âOSlog nâO<+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) ⥠â^S{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) ⥠Ω(â^Sm).
- 关键词：Set membership; Bit-probe model; Fully-explicit data structures; Adaptive data structures; Error-correcting codes
