A Recursive Framework for Evaluating Moments Using Zero-Suppressed Binary Decision Diagrams

Abstract

The zero-suppressed binary decision diagram (ZDD) is a compact data structure widely used for the efficient representation of families of sparse subsets. Its inherent recursive structure also facilitates easy diagram manipulation and family operations. Practical applications generally fall under discrete optimization, such as combinatorial problems and graph theory. Given its utility, summarizing the subsets represented in the diagram using key metrics is of great value as this provides valuable insights into the characteristics of the family. The paper proposes a recursive algorithm to extract information on moments from families represented as a ZDD. Given a value for every element in the universe, the value of a subset is first formulated as the sum of the values of its elements. The moments of a family are then calculated as the mean of the exponentiated subset values, akin to the method of moments. Leveraging the structure of the ZDD, the proposed algorithm recursively traverses a given diagram for efficient moments evaluation via multinomial expansion. Its utility is then demonstrated with three classical problems—power sets, the knapsack problem, and paths in graphs—offering orders of magnitude increase in computational efficiency relative to conventional method. Overall, the proposed algorithm enhances the functionality of the ZDD by introducing an efficient family operation to uncover the distribution of subset values in a represented family.

Keywords

• Discrete optimization
• family operation
• method of moments
• zero-suppressed binary decision diagram