Compressing Configuration Data for Memory Limited Devices

Abstract

The paper introduces a new type of compression for de-cision diagram data structures, such as BDDs, MDDs and AOMDDs. The compression takes advantage of repeated substructures within the decision diagram in order to lessen redundancy beyond what is possible using simple subfunc-tion sharing. The resulting compressed data structure allows traversal of the original decision diagram with no significant overhead. Specifically it allows the efficient computation of valid domains, that is, the assignments for each encoded vari-able that can participate in a solution, which is critical when the decision diagram is used to support an interactive config-urator. We relate these results to applications for interactively configurable memory limited devices and give empirical re-sults on the amount of saved space for a wide variety of in-stances.