Document Open Access Logo

Space-Efficient Data Structures for Lattices

Authors J. Ian Munro , Bryce Sandlund, Corwin Sinnamon

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.31.pdf
  • Filesize: 0.61 MB
  • 22 pages

Document Identifiers

Author Details

J. Ian Munro
  • Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Bryce Sandlund
  • Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Corwin Sinnamon
  • Department of Computer Science, Princeton University, Princeton, NJ 08540, USA

Funding

This work was supported by the Natural Sciences and Engineering Research Council of Canada and the Canada Research Chairs Program.

Cite As Get BibTex

J. Ian Munro, Bryce Sandlund, and Corwin Sinnamon. Space-Efficient Data Structures for Lattices. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.31

Abstract

A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity.

Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in O(n^{3/4}) time, where n is the number of elements in the lattice. It occupies O(n^{3/2}log n) bits of space, which is only a Θ(log n) factor from the Θ(n^{3/2})-bit lower bound for storing lattices. The preprocessing time is O(n²). This structure admits a simple space-time tradeoff so that, for any c ∈ [1/2, 1], the data structure supports meet and join queries in O(n^{1-c/2}) time, occupies O(n^{1+c}log n) bits of space, and can be constructed in O(n² + n^{1+3c/2}) time.

Our second data structure uses O(n^{3/2}log n) bits of space and supports meet and join in O(d (log n)/(log d)) time, where d is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements.

This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Mathematics of computing → Graph algorithms
Keywords
  • Lattice
  • Partially-ordered set
  • Space-efficient data structure
  • Succinct data structure

Metrics

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

References

  1. Hassan Aït-Kaci, Robert Boyer, Patrick Lincoln, and Roger Nasr. Efficient implementation of lattice operations. ACM Transactions on Programming Languages and Systems (TOPLAS), 11(1):115-146, 1989. Google Scholar
  2. Garrett Birkhoff. Rings of sets. Duke Mathematical Journal, 3(3):443-454, 1937. Google Scholar
  3. Andrej Brodnik and J Ian Munro. Membership in constant time and almost-minimum space. SIAM Journal on Computing, 28(5):1627-1640, 1999. Google Scholar
  4. Yves Caseau. Efficient handling of multiple inheritance hierarchies. ACM SIGPLAN Notices, 28(10):271-287, 1993. Google Scholar
  5. Yves Caseau, Michel Habib, Lhouari Nourine, and Olivier Raynaud. Encoding of multiple inheritance hierarchies and partial orders. Computational Intelligence, 15(1):50-62, 1999. Google Scholar
  6. Marcel Erné, Jobst Heitzig, and Jürgen Reinhold. On the number of distributive lattices. Electron. J. Combin, 9(1):23, 2002. Google Scholar
  7. Arash Farzan and J Ian Munro. Succinct representation of finite abelian groups. In Proceedings of the 2006 international symposium on Symbolic and algebraic computation, pages 87-92. ACM, 2006. Google Scholar
  8. Bernhard Ganter, Gerd Stumme, and Rudolf Wille. Formal concept analysis: foundations and applications, volume 3626. Springer, 2005. Google Scholar
  9. George Grätzer and Friedrich Wehrung. Lattice theory: special topics and applications. Springer, 2016. Google Scholar
  10. Michel Habib, Raoul Medina, Lhouari Nourine, and George Steiner. Efficient algorithms on distributive lattices. Discrete Applied Mathematics, 110(2):169-187, 2001. Google Scholar
  11. Michel Habib and Lhouari Nourine. Tree structure for distributive lattices and its applications. Theoretical Computer Science, 165(2):391-405, 1996. Google Scholar
  12. Arthur B Kahn. Topological sorting of large networks. Communications of the ACM, 5(11):558-562, 1962. Google Scholar
  13. DJ Kleitman and KJ Winston. The asymptotic number of lattices. Annals of Discrete Mathematics, 6:243-249, 1980. Google Scholar
  14. Walter Klotz and Lutz Lucht. Endliche verbände. Journal für die Reine und Angewandte Mathematik, 247:58-68, 1971. Google Scholar
  15. Andreas Krall, Jan Vitek, and R Nigel Horspool. Near optimal hierarchical encoding of types. In European Conference on Object-Oriented Programming, pages 128-145. Springer, 1997. Google Scholar
  16. Bernard Monjardet. The presence of lattice theory in discrete problems of mathematical social sciences. Why? Mathematical Social Sciences, 46(2):103-144, 2003. Google Scholar
  17. J Ian Munro and Corwin Sinnamon. Time and space efficient representations of distributive lattices. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 550-567. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  18. Flemming Nielson, Hanne R Nielson, and Chris Hankin. Principles of program analysis. Springer, 2015. Google Scholar
  19. Mihai Pătraşcu. Unifying the landscape of cell-probe lower bounds. SIAM Journal on Computing, 40(3):827-847, 2011. Google Scholar
  20. Maurizio Talamo and Paola Vocca. Fast lattice browsing on sparse representation. In Orders, Algorithms, and Applications, pages 186-204. Springer, 1994. Google Scholar
  21. Maurizio Talamo and Paola Vocca. A data structure for lattice representation. Theoretical Computer Science, 175(2):373-392, 1997. Google Scholar
  22. Maurizio Talamo and Paola Vocca. An efficient data structure for lattice operations. SIAM journal on computing, 28(5):1783-1805, 1999. Google Scholar
  23. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM (JACM), 51(6):993-1024, 2004. Google Scholar
  24. Rudolf Wille. Restructuring lattice theory: an approach based on hierarchies of concepts. In Ordered sets, pages 445-470. Springer, 1982. Google Scholar
  25. Kenneth James Winston. Asymptotic analysis of lattices and tournament score vectors. PhD thesis, Massachusetts Institute of Technology, 1979. 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 About DROPS Imprint Privacy Contact