LIPIcs.FSTTCS.2018.12.pdf
- Filesize: 393 kB
- 12 pages
Document
Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements
Author
-
Part of:
Volume:
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-05
Cite AsGet BibTex
Deepanjan Kesh. Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.12
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.12
Abstract
We consider the following set membership problem in the bitprobe model - that of storing subsets of size at most three from a universe of size m, and answering membership queries using two adaptive bitprobes. Baig and Kesh [Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2018] proposed a scheme for the problem which takes O(m^{2/3}) space. In this paper, we present a proof which shows that any scheme for the problem requires Omega(m^{2/3}) amount of space. These two results together settle the space complexity issue for this particular problem.
Subject Classification
ACM Subject Classification
- Information systems → Data structures
Keywords
- Data structures
- set membership problem
- bitprobe model
- lower bound
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Noga Alon and Uriel Feige. On the power of two, three and four probes. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 346-354, 2009.
-
Mirza Galib Anwarul Husain Baig and Deepanjan Kesh. Two New Schemes in the Bitprobe Model. In WALCOM: Algorithms and Computation - 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings, pages 68-79, 2018.
-
Mohit Garg. The Bit-probe Complexity of Set Membership. PhD thesis, School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Navy Nagar, Colaba, Mumbai 400005, India, 2016.
-
Mohit Garg and Jaikumar Radhakrishnan. Set membership with a few bit probes. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 776-784, 2015.
-
Moshe Lewenstein, J. Ian Munro, Patrick K. Nicholson, and Venkatesh Raman. Improved Explicit Data Structures in the Bitprobe Model. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 630-641, 2014.
-
Jaikumar Radhakrishnan, Venkatesh Raman, and S. Srinivasa Rao. Explicit Deterministic Constructions for Membership in the Bitprobe Model. In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, pages 290-299, 2001.
-
Jaikumar Radhakrishnan, Smit Shah, and Saswata Shannigrahi. Data Structures for Storing Small Sets in the Bitprobe Model. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II, pages 159-170, 2010.