article

Are Bitvectors Optimal?

Authors:

H. Buhrman,

P. B. Miltersen,

J. Radhakrishnan,

S. VenkateshAuthors Info & Claims

SIAM Journal on Computing, Volume 31, Issue 6

Pages 1723 - 1744

https://doi.org/10.1137/S0097539702405292

Published: 01 June 2002 Publication History

Publisher Site

Abstract

We study the it static membership problem : Given a set S of at most n keys drawn from a universe U of size m , store it so that queries of the form "Is u in S __ __" can be answered by making few accesses to the memory. We study schemes for this problem that use space close to the information theoretic lower bound of $\Omega(n\log(\frac{m}{n}))$ bits and yet answer queries by reading a small number of bits of the memory.

We show that, for $\epsilon > 0$, there is a scheme that stores $O(\frac{n}{\epsilon^2}\log m)$ bits and answers membership queries using a randomized algorithm that reads just one bit of memory and errs with probability at most $\epsilon$. We consider schemes that make no error for queries in S but are allowed to err with probability at most $\epsilon$ for queries not in S . We show that there exist such schemes that store $O((\frac{n}{\epsilon})^2 \log m)$ bits and answer queries using just one bitprobe. If multiple probes are allowed, then the number of bits stored can be reduced to $O(n^{1+\delta}\log m)$ for any $\delta > 0$. The schemes mentioned above are based on probabilistic constructions of set systems with small intersections.

We show lower bounds that come close to our upper bounds (for a large range of n and $\epsilon$): Schemes that answer queries with just one bitprobe and error probability $\epsilon$ must use $\Omega(\frac{n}{\epsilon\log(1/\epsilon)} \log m)$ bits of storage; if the error is restricted to queries not in S , then the scheme must use $\Omega(\frac{n^2}{\epsilon^2 \log (n/\epsilon)}\log m)$ bits of storage.

We also consider deterministic schemes for the static membership problem and show tradeoffs between space and the number of probes.

Cited By

View all

Rescigno AVaccaro U(2024)Improved Algorithms and Bounds for List Union-Free FamiliesIEEE Transactions on Information Theory10.1109/TIT.2023.331643570:4(2456-2463)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3316435
Vatedka SChandar VTchamkerten A(2022)Locally Decodable Slepian-Wolf Compression2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834371(1430-1435)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834371
Sen P(2021)An efficient superpostional quantum Johnson–Lindenstrauss lemma via unitary t-designsQuantum Information Processing10.1007/s11128-021-03238-220:9Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s11128-021-03238-2
Show More Cited By

Index Terms

Are Bitvectors Optimal?

Recommendations

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to ...
Cache-oblivious range reporting with optimal queries requires superlinear space
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(log_BN + K/B) block ...
Two-dimensional range successor in optimal time and almost linear space

In this article, we revisit the problem of supporting two-dimensional range successor queries. We present a data structure with O ( n lg lg n ) words of space and O ( lg lg n ) query time. This improves the work of Nekrich and Navarro (2012) by a factor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 31, Issue 6

2002

314 pages

ISSN:0097-5397

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 June 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rescigno AVaccaro U(2024)Improved Algorithms and Bounds for List Union-Free FamiliesIEEE Transactions on Information Theory10.1109/TIT.2023.331643570:4(2456-2463)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3316435
Vatedka SChandar VTchamkerten A(2022)Locally Decodable Slepian-Wolf Compression2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834371(1430-1435)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834371
Sen P(2021)An efficient superpostional quantum Johnson–Lindenstrauss lemma via unitary t-designsQuantum Information Processing10.1007/s11128-021-03238-220:9Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s11128-021-03238-2
Yu HMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Nearly optimal static Las Vegas succinct dictionaryProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384274(1389-1401)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384274
Vatedka SChandar VTchamkerten A(2020)O (log log n) Worst-Case Local Decoding and Update Efficiency for Data Compression2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9173968(2371-2376)Online publication date: 21-Jun-2020
https://dl.acm.org/doi/10.1109/ISIT44484.2020.9173968
Vatedka STchamkerten A(2019)Local Decoding and Update of Compressed Data2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849634(572-576)Online publication date: 7-Jul-2019
https://dl.acm.org/doi/10.1109/ISIT.2019.8849634
Kesh DSharma V(2019)On the Bitprobe Complexity of Two Probe Adaptive Schemes Storing Two ElementsAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-11509-8_5(53-64)Online publication date: 14-Feb-2019
https://dl.acm.org/doi/10.1007/978-3-030-11509-8_5
Baig MKesh DSodani C(2019)A Two Query Adaptive Bitprobe Scheme Storing Five ElementsWALCOM: Algorithms and Computation10.1007/978-3-030-10564-8_25(317-328)Online publication date: 27-Feb-2019
https://dl.acm.org/doi/10.1007/978-3-030-10564-8_25
Tatwawadi KBidokhti SWeissman T(2018)On Universal Compression with Constant Random Access2018 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2018.8437931(891-895)Online publication date: 17-Jun-2018
https://dl.acm.org/doi/10.1109/ISIT.2018.8437931
Damaschke P(2018)Saving Probe Bits by Cube DominationGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-00256-5_12(139-151)Online publication date: 27-Jun-2018
https://dl.acm.org/doi/10.1007/978-3-030-00256-5_12
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Towards optimal range medians

Cache-oblivious range reporting with optimal queries requires superlinear space

Two-dimensional range successor in optimal time and almost linear space

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations