A Constant-Time Colored Choice Dictionary with Almost Robust Iteration

Author Torben Hagerup



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.64.pdf
  • Filesize: 497 kB
  • 14 pages

Document Identifiers

Author Details

Torben Hagerup
  • Institut für Informatik, Universität Augsburg, 86135 Augsburg, Germany

Cite AsGet BibTex

Torben Hagerup. A Constant-Time Colored Choice Dictionary with Almost Robust Iteration. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.64

Abstract

A (colored) choice dictionary is a data structure that is initialized with positive integers n and c and subsequently maintains a sequence of n elements of {0,...,c-1}, called colors, under operations to inspect and to update the color in a given position and to return the position of an occurrence of a given color. Choice dictionaries are fundamental in space-efficient computing. Some applications call for the additional operation of dynamic iteration, i.e., enumeration of the positions containing a given color while the sequence of colors may change. An iteration is robust if it enumerates every position that contains the relevant color throughout the iteration but never enumerates a position more than once or when it does not contain the color in question. We describe the first choice dictionary that executes every operation in constant amortized time and almost robust iteration in constant amortized time per element enumerated. The iteration is robust, except that it may enumerate some elements a second time. The data structure occupies n log_2 c+O((log n)^2) bits. The time and space bounds assume that c=O((log n)^{1/2}(log log n)^{-{3/2}}).

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Succinct data structures
  • space efficiency
  • in-place chain technique
  • bounded universes
  • amortization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. D. Angluin and L. G. Valiant. Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings. J. Comput. Syst. Sci., 18(2):155-193, 1979. URL: https://doi.org/10.1016/0022-0000(79)90045-X.
  2. Niranka Banerjee, Sankardeep Chakraborty, and Venkatesh Raman. Improved Space Efficient Algorithms for BFS, DFS and Applications. In Proc. 22nd International Conference on Computing and Combinatorics (COCOON 2016), volume 9797 of LNCS, pages 119-130. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-42634-1_10.
  3. Preston Briggs and Linda Torczon. An Efficient Representation for Sparse Sets. ACM Lett. Program. Lang. Syst., 2(1-4):59-69, 1993. URL: https://doi.org/10.1145/176454.176484.
  4. Yevgeniy Dodis, Mihai Pǎtraşcu, and Mikkel Thorup. Changing Base Without Losing Space. In Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 593-602. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806770.
  5. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-Efficient Basic Graph Algorithms. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of LIPIcs, pages 288-301. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.288.
  6. Torben Hagerup. Sorting and Searching on the Word RAM. In Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), volume 1373 of LNCS, pages 366-398. Springer, 1998. URL: https://doi.org/10.1007/BFb0028575.
  7. Torben Hagerup. Small Uncolored and Colored Choice Dictionaries. Computing Research Repository (CoRR), abs/1809.07661 [cs.DS], 2018. URL: http://arxiv.org/abs/1809.07661.
  8. Torben Hagerup. Highly Succinct Dynamic Data Structures. In Leszek Antoni Gasieniec, Jesper Jansson, and Christos Levcopoulos, editors, Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings, volume 11651 of Lecture Notes in Computer Science, pages 29-45. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-25027-0_3.
  9. Torben Hagerup. Fast Breadth-First Search in Still Less Space. In Proc. 45th International Workhop on Graph-Theoretic Concepts in Computer Science (WG 2019), LNCS. Springer, 2019, to appear. Google Scholar
  10. Torben Hagerup and Frank Kammer. Succinct Choice Dictionaries. Computing Research Repository (CoRR), abs/1604.06058 [cs.DS], 2016. URL: http://arxiv.org/abs/1604.06058.
  11. Torben Hagerup, Frank Kammer, and Moritz Laudahn. Space-Efficient Euler Partition and Bipartite Edge Coloring. Theor. Comput. Sci., 754:16-34, 2019. URL: https://doi.org/10.1016/j.tcs.2018.01.008.
  12. Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. Algorithmica, 81(3):1180-1204, 2019. URL: https://doi.org/10.1007/s00453-018-0464-z.
  13. Frank Kammer and Andrej Sajenko. Simple 2^f-Color Choice Dictionaries. In Proc. 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of LIPIcs, pages 66:1-66:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  14. Takashi Katoh and Keisuke Goto. In-Place Initializable Arrays. Computing Research Repository (CoRR), abs/1709.08900 [cs.DS], 2017. URL: http://arxiv.org/abs/1709.08900.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail