Document Open Access Logo

Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays

Authors Frank Kammer, Andrej Sajenko

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.65.pdf
  • Filesize: 476 kB
  • 16 pages

Document Identifiers

Author Details

Frank Kammer
  • THM, University of Applied Sciences Mittelhessen, Germany
Andrej Sajenko
  • THM, University of Applied Sciences Mittelhessen, Germany

Funding

  • Sajenko, Andrej: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 379157101.

Cite AsGet BibTex

Frank Kammer and Andrej Sajenko. Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.65

Abstract

Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data structure is not initialized, i.e., there is plenty of unused space allocated for the data structure. We present a general framework to store temporarily extra buffers between the user defined data so that the data can be processed immediately, stored first in the buffers, and then moved into the data structure after finishing the tables. As an application, we apply our framework to Dodis, Patrascu, and Thorup's data structure (STOC 2010) that emulates c-ary memory and to Farzan and Munro's succinct encoding of arbitrary graphs (TCS 2013). We also use our framework to present an in-place dynamical initializable array.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • space efficiency
  • succinct c-ary memory
  • dynamic graph representation

Metrics

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

References

  1. Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz. Reprint of: Memory-constrained algorithms for simple polygons. Comput. Geom. Theory Appl., 47(3, Part B):469-479, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2013.11.004.
  2. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search using O(n) bits. In Proc. 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 553-564. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_44.
  3. Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira, and Kunihiko Sadakane. Space-time trade-offs for stack-based algorithms. In Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of LIPIcs, pages 281-292. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.281.
  4. Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991. URL: http://dx.doi.org/10.1137/0220017.
  5. Jon Bentley. Programming Pearls. ACM, New York, NY, USA, 1986. Google Scholar
  6. Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. Frameworks for designing in-place graph algorithms. CoRR, abs/1711.09859, 2017. URL: http://arxiv.org/abs/1711.09859.
  7. Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of LIPIcs, pages 28:1-28:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.28.
  8. 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: http://dx.doi.org/10.1145/1806689.1806770.
  9. 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: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  10. Amr Elmasry and Frank Kammer. Space-efficient plane-sweep algorithms. In Proc. 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 of LIPIcs, pages 30:1-30:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.30.
  11. Arash Farzan and J. Ian Munro. Succinct encoding of arbitrary graphs. Theor. Comput. Sci., 513:38-52, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.09.031.
  12. Torben Hagerup and Frank Kammer. Succinct choice dictionaries. Computing Research Repository (CoRR), arXiv:1604.06058 [cs.DS], 2016. URL: http://arxiv.org/abs/1604.06058.
  13. Torben Hagerup and Frank Kammer. On-the-fly array initialization in less space. In Proc. 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of LIPIcs, pages 44:1-44:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.44.
  14. Torben Hagerup, Frank Kammer, and Moritz Laudahn. Space-efficient Euler partition and bipartite edge coloring. Theor. Comput. Sci., to appear, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2018.01.008.
  15. Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of LIPIcs, pages 56:1-56:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.56.
  16. Frank Kammer and Andrej Sajenko. Linear-time in-place DFS and BFS in the restore model. Computing Research Repository (CoRR), arXiv:1803.04282 [cs.DS], 2018. URL: http://arxiv.org/abs/1803.04282.
  17. Takashi Katoh and Keisuke Goto. In-place initializable arrays. Computing Research Repository (CoRR), arXiv:1709.08900 [cs.DS], 2017. URL: http://arxiv.org/abs/1709.08900.
  18. Veli Mäkinen and Gonzalo Navarro. Dynamic entropy-compressed sequences and full-text indexes. ACM Trans. Algorithms, 4(3), 2008. URL: http://dx.doi.org/10.1145/1367064.1367072.
  19. Kurt Mehlhorn. Data structures and algorithms 1: Sorting and searching. In EATCS Monographs Theor. Comput. Sci., 1984. Google Scholar
  20. J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct representations of permutations and functions. Theor. Comput. Sci., 438:74-88, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.005.
  21. Gonzalo Navarro. Spaces, trees, and colors: The algorithmic landscape of document retrieval on sequences. ACM Comput. Surv., 46(4):52:1-52:47, 2014. URL: http://dx.doi.org/10.1145/2535933.
  22. Rasmus Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. Comput., 31(2):353-363, 2001. URL: http://dx.doi.org/10.1137/S0097539700369909.
  23. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998), pages 264-268. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743455.
  24. Mihai Pǎtraşcu. Succincter. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 305-313. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.83.
  25. Mihai Pǎtraşcu and Mikkel Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In Proc. 55th IEEE Annual Symposium on Foundations of Computer Science, (FOCS 2014), pages 166-175. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.26.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact