Efficient Representation and Encoding of Distributive Lattices

succinct data structure;compact data structure;lattice;distributive lattice;partially-ordered set;persistence

Sinnamon, Corwinadvisor:Munro, J. Ian ; affiliation1:Faculty of Mathematics ; Munro, J. Ian ;

University of Waterloo

关键词: succinct data structure;    Master Thesis;    partially-ordered set;    lattice;    distributive lattice;    persistence;    compact data structure;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13609/1/Sinnamon_Corwin.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis presents two new representations of distributive lattices with an eye towards efficiency in both time and space. Distributive lattices are a well-known class of partially-ordered sets having two natural operations called meet and join.Improving on all previous results, we develop an efficient data structure for distributive lattices that supports meet and join operations in O(log n) time, where n is the size of the lattice. The structure occupies O(n log n) bits of space, which is as compact as any known data structure and within a logarithmic factor of the information-theoretic lower bound byenumeration.The second representation is a bitstring encoding of a distributive lattice that uses approximately 1.26n bits. This is within a small constant factor of the best known upper and lower bounds for this problem. A lattice can be encoded or decoded in O(n log n) time.