License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.6
URN: urn:nbn:de:0030-drops-120809
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12080/
Go to the corresponding LIPIcs Volume Portal

Matsuda, Kotaro ; Denzumi, Shuhei ; Sadakane, Kunihiko

Storing Set Families More Compactly with Top ZDDs

pdf-format:
LIPIcs-SEA-2020-6.pdf (0.6 MB)

Abstract

Zero-suppressed Binary Decision Diagrams (ZDDs) are data structures for representing set families in a compressed form. With ZDDs, many valuable operations on set families can be done in time polynomial in ZDD size. In some cases, however, the size of ZDDs for representing large set families becomes too huge to store them in the main memory.
This paper proposes top ZDD, a novel representation of ZDDs which uses less space than existing ones. The top ZDD is an extension of top tree, which compresses trees, to compress directed acyclic graphs by sharing identical subgraphs. We prove that navigational operations on ZDDs can be done in time poly-logarithmic in ZDD size, and show that there exist set families for which the size of the top ZDD is exponentially smaller than that of the ZDD. We also show experimentally that our top ZDDs have smaller size than ZDDs for real data.

BibTeX - Entry

@InProceedings{matsuda_et_al:LIPIcs:2020:12080,
  author =	{Kotaro Matsuda and Shuhei Denzumi and Kunihiko Sadakane},
  title =	{{Storing Set Families More Compactly with Top ZDDs}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12080},
  URN =		{urn:nbn:de:0030-drops-120809},
  doi =		{10.4230/LIPIcs.SEA.2020.6},
  annote =	{Keywords: top tree, Zero-suppressed Decision Diagram, space-efficient data structure}
}

Keywords: top tree, Zero-suppressed Decision Diagram, space-efficient data structure
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI