论文标题
用顶级ZDD更紧凑地存储套装家庭
Storing Set Families More Compactly with Top ZDDs
论文作者
论文摘要
零抑制的二进制决策图（ZDDS）是用于以压缩形式代表套件的数据结构。借助ZDD，可以在ZDD大小的多项式上进行许多有关集合家庭的宝贵操作。但是，在某些情况下，代表大型家族的ZDD的大小变得太大，无法将其存储在主内存中。本文提出了Top ZDD，这是ZDD的新颖表示，它使用的空间比现有空间少。顶部ZDD是顶部树的扩展，它可以通过共享相同的子图来压缩树木，以压缩有向的无环图。我们证明，可以在ZDD上进行导航操作，可以在时间poly-logarithmicin ZDD大小上进行，并证明存在设定的家族，顶部ZDD的大小比ZDD的大小要小。我们还通过实验表明，对于真实数据，我们的顶级ZDD的尺寸小于ZDD。
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.
