# Storing Set Families More Compactly with Top ZDDs
## 1 Introduction  
Zero-suppressed Binary Decision Diagrams (ZDDs) [1] are data structures which are derived from Binary Decision Diagrams (BDDs) [2] and represent a family of sets (combinatorial sets) in a compressed form using Directed Acyclic Graphs (DAGs). ZDDs are data structures specialized for processing set families and it is known that sparse set families can be compressed well. ZDDs support binary operations between two families of sets in time polynomial in the size of the ZDDs. Because of these advantages, ZDDs are used for combinatorial optimization problems and enumeration problems. Although ZDDs were originally developed for VLSI logic design, it has been shown that they can also be used effectively for graph problems and combinatorial problems because set families are a fundamental concept that appears in various fields [3, 4]. Various other application researches related to intelligent information processing have been published, for example, in the fields of data mining [5, 6, 7], probabilistic graphical models such as Bayesian network [8, 9], and game theory [10].  
Though ZDDs can store set families compactly, their size may grow for some set families, and we need further compression. DenseZDDs [11] are data structures for storing ZDDs in a compressed form and supporting operations on the compressed representation. DenseZDDs represent a ZDD by a spanning tree of the DAG representing it, and an array of pointers between nodes on the spanning tree. Therefore its size is always linear to the original size, and to compress more, we need another representation.  
Our basic idea for compression is as follows. In a ZDD, the identical sub-structures are shared and replaced by pointers. However identical sub-structures cannot be shared if they appear at different heights in ZDD. As a result, even if the DAG of a ZDD contains repetitive structures in the height direction, they cannot be shared.  
For not DAGs but trees, there exists a data structure called top DAG compression [12], which can capture repetitive structures in the height direction. We extend it for DAGs and apply it to compress ZDDs which support the operations on compressed ZDDs.  
This paper is an extended version of a conference paper published in SEA 2020 [13]. We rewrote the previous work so that readers not familiar with compression methods and operations on compressed data structure can understand our results easily. We added explanations of the DAG compression and how our algorithms work on compressed data with pseudo-codes. We also complement proof of space complexity.  
The organization of the paper is as follows. In Section 2, we introduce our notation and data structures used throughout this paper. In Section 3, we introduce top trees and top DAGs. We show how to construct them and what operations they can perform. In Section 4, we propose our data structure, Top ZDD, and present the detailed components of Top ZDD, the theoretical analysis of the size, and the implementation method of the operations. In Section 5, we show the results of experiments for real and artificial data to evaluate construction time, search time and compactness of DenseZDDs. In Section 5, we show the experimental results on real and artificial data and compare Top ZDD, DenseZDD and standard ZDD to confirm the performance of the proposed method. In Section 6, we summarize the overall contents of this paper and discuss future work.