Storing Set Families More Compactly with Top ZDDs
Preprint
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-logarithmicin 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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Fully Functional Static and Dynamic Succinct TreesACM Transactions on Algorithms, 2014
- DenseZDD: A Compact and Fast Index for Families of SetsLecture Notes in Computer Science, 2014
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisetsACM Transactions on Algorithms, 2007
- Practical Entropy-Compressed Rank/Select Dictionary2007
- Maintaining information in fully dynamic trees with top treesACM Transactions on Algorithms, 2005
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String MatchingSIAM Journal on Computing, 2005
- Query evaluation on compressed trees2003
- Zero-suppressed BDDs for set manipulation in combinatorial problems1993
- Shared binary decision diagram with attributed edges for efficient Boolean function manipulation1990
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980