Document Open Access Logo

Space-Efficient Data Structure for Posets with Applications

Authors Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane , Srinivasa Rao Satti

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.33.pdf
  • Filesize: 0.75 MB
  • 16 pages

Document Identifiers

Author Details

Tatsuya Yanagita
  • The University of Tokyo, Japan
Sankardeep Chakraborty
  • The University of Tokyo, Japan
Kunihiko Sadakane
  • The University of Tokyo, Japan
Srinivasa Rao Satti
  • Norwegian University of Science and Technology, Trondheim, Norway

Cite AsGet BibTex

Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Space-Efficient Data Structure for Posets with Applications. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.33

Abstract

Space efficient data structures for partial ordered sets or posets are well-researched field. It is known that a poset with n elements can be represented in n²/4 + o(n²) bits [Munro and Nicholson, 2016] and can also be represented in (1 + ε)n log n + 2nk + o(nk) bits [Farzan and Fischer, 2011] where k is width of the poset. In this paper, we make the latter data structure occupy 2n(k-1) + o(nk) bits by considering topological labeling on the elements of posets. Also considering the topological labeling, we propose a new data structure that calculates queries on transitive reduction graphs of posets faster though queries on transitive closure graphs are computed slower. Moreover, we propose an alternative data structure for topological labeled posets that calculates both of the queries faster though it uses 3nk - 2n + o(nk) bits of space. Additionally, we discuss the advantage of these data structures from the perspective of an application for BlockDAG, which is a more scalable version of Blockchain.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Succinct Data Structures
  • Posets
  • Blockchain

Metrics

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

References

  1. H. Acan, S. Chakraborty, S. Jo, K. Nakashima, K. Sadakane, and S. R. Satti. Succinct representations of intersection graphs on a circle. In 31st Data Compression Conference, DCC 2021, Snowbird, UT, USA, March 23-26, 2021, pages 123-132. IEEE, 2021. Google Scholar
  2. H. Acan, S. Chakraborty, S. Jo, and S. R. Satti. Succinct data structures for families of interval graphs. In Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 1-13. Springer, 2019. Google Scholar
  3. A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2):131-137, 1972. Google Scholar
  4. J. Alman and V. V. Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539. ACM-SIAM, 2021. Google Scholar
  5. J. Balabán and P. Hliněný. Twin-width is linear in the poset width. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), volume 214 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:13, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
  6. J. Barbay, F. Claude, and G. Navarro. Compact binary relation representations with rich functionality. Information and Computation, 232:19-37, 2013. Google Scholar
  7. J. Barbay, M. He, J. I. Munro, and S. R. Satti. Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms, 7(4), 2011. Google Scholar
  8. Garrett Birkhoff. On the structure of abstract algebras. Mathematical Proceedings of the Cambridge Philosophical Society, 31(4):433-454, 1935. Google Scholar
  9. É. Bonnet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width I: Tractable FO model checking. Journal of the ACM, 69(1), 2021. Google Scholar
  10. G. Brightwell and S. Goodall. The number of partial orders of fixed width. Order, 13(4):315-337, 1996. Google Scholar
  11. A. Brodnik and J. I. Munro. Membership in constant time and almost-minimum space. SIAM Journal on Computing, 28(5):1627-1640, 1999. Google Scholar
  12. S. Chakraborty, S. Jo, K. Sadakane, and S. R. Satti. Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs. In Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings, volume 13135 of Lecture Notes in Computer Science, pages 416-430. Springer, 2021. Google Scholar
  13. S. Chakraborty, S. Jo, K. Sadakane, and S. R. Satti. Succinct data structures for small clique-width graphs. In 31st Data Compression Conference, DCC 2021, Snowbird, UT, USA, March 23-26, 2021, pages 133-142. IEEE, 2021. Google Scholar
  14. Y. Chen and Y. Chen. On the DAG decomposition. British Journal of Mathematics & Computer Science, 10:1-27, 2015. Google Scholar
  15. C. Daskalakis, R. M. Karp, E. Mossel, S. J. Riesenfeld, and E. Verbin. Sorting and selection in posets. SIAM Journal on Computing, 40(3):597-622, 2011. Google Scholar
  16. R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161-166, 1950. Google Scholar
  17. J. R. Driscoll, H. N. Gabow, R. Shrairman, and R. E. Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343-1354, 1988. Google Scholar
  18. M. Erné, J. Heitzig, and J. Reinhold. On the number of distributive lattices. The Electronic Journal of Combinatorics, 9, 2002. Google Scholar
  19. A. Farzan and J. Fischer. Compact representation of posets. In Proceedings of the 22nd International Conference on Algorithms and Computation (ISAAC), pages 302-311, Berlin, Heidelberg, 2011. Springer-Verlag. Google Scholar
  20. A. Farzan and J. I. Munro. Succinct encoding of arbitrary graphs. Theoretical Computer Science, 513:38-52, 2013. Google Scholar
  21. M. J. Fischer and A. R. Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual Symposium on Switching and Automata Theory (swat 1971), pages 129-131, 1971. Google Scholar
  22. M. L. Fredman and D. E. Willard. Blasting through the information theoretic barrier with fusion trees. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC), pages 1-7, New York, NY, USA, 1990. Google Scholar
  23. D. R. Fulkerson. Note on Dilworth’s decomposition theorem for partially ordered sets. Proceedings of the American Mathematical Society, 7(4), 1956. Google Scholar
  24. A. Golynski, J. I. Munro, and S. R. Satti. Rank/select operations on large alphabets: A tool for text indexing. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pages 368-373, USA, 2006. Society for Industrial and Applied Mathematics. Google Scholar
  25. A. Goralčíková and V. Koubek. A reduct-and-closure algorithm for graphs. In Mathematical Foundations of Computer Science 1979, pages 301-307, Berlin, Heidelberg, 1979. Springer Berlin Heidelberg. Google Scholar
  26. R. Grossi, A. Gupta, and J. S. Vitter. High-order entropy-compressed text indexes. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 841-850, USA, 2003. Society for Industrial and Applied Mathematics. Google Scholar
  27. J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973. Google Scholar
  28. G. J. Jacobson. Succinct Static Data Structures. PhD thesis, Carnegie Mellon University, USA, 1988. AAI8918056. Google Scholar
  29. D. J. Kleitman and B. L. Rothschild. Asymptotic enumeration of partial orders on a finite set. Transactions of the American Mathematical Society, 205:205-220, 1975. Google Scholar
  30. J. I. Munro and P. K. Nicholson. Succinct posets. Algorithmica, 76(2):445-473, 2016. Google Scholar
  31. J. I. Munro, R. Raman, V. Raman, and S. R. Satti. Succinct representations of permutations and functions. Theoretical Computer Science, 438:74-88, 2012. Google Scholar
  32. J. I. Munro and C. Sinnamon. Time and space efficient representations of distributive lattices. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 550-567. ACM-SIAM, 2018. Google Scholar
  33. J. I. Munro and K. Wu. Succinct data structures for chordal graphs. In 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pages 67:1-67:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  34. S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Cryptography Mailing list at https://metzdowd.com, 2009. URL: https://bitcoin.org/bitcoin.pdf.
  35. R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing, 31(2):353-363, 2001. Google Scholar
  36. M. Pilipczuk, M. Sokołowski, and A. Zych-Pawlewicz. Compact representation for matrices of bounded twin-width. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 52:1-52:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
  37. Y. Sompolinsky, S. Wyborski, and A. Zohar. Phantom ghostdag: A scalable generalization of Nakamoto consensus: September 2, 2021. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 57-70, New York, NY, USA, 2021. Google Scholar
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