Back to search

University of Waterloo

Efficient Representation and Encoding of Distributive Lattices

Abstract

dc:description.abstract

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 by enumeration. 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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sinnamon, Corwin
Advisor dc:contributor.advisor
  • Munro, J. Ian

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/13609

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sinnamon, Corwin. Efficient Representation and Encoding of Distributive Lattices. University of Waterloo, 2018. http://hdl.handle.net/10012/13609