Munro, J. Ian ;
Sandlund, Bryce ;
Sinnamon, Corwin
SpaceEfficient Data Structures for Lattices
Abstract
A lattice is a partiallyordered 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 spacetime tradeoff so that, for any c ∈ [1/2, 1], the data structure supports meet and join queries in O(n^{1c/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 lowdegree elements.
This paper also identifies an error in a longstanding solution to the problem of representing lattices. We discuss the issue with this previous work.
BibTeX  Entry
@InProceedings{munro_et_al:LIPIcs:2020:12278,
author = {J. Ian Munro and Bryce Sandlund and Corwin Sinnamon},
title = {{SpaceEfficient Data Structures for Lattices}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {31:131:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12278},
URN = {urn:nbn:de:0030drops122782},
doi = {10.4230/LIPIcs.SWAT.2020.31},
annote = {Keywords: Lattice, Partiallyordered set, Spaceefficient data structure, Succinct data structure}
}
12.06.2020
Keywords: 

Lattice, Partiallyordered set, Spaceefficient data structure, Succinct data structure 
Seminar: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Issue date: 

2020 
Date of publication: 

12.06.2020 