The paper introduces a new technique for compressing Binary Decision Diagrams in those cases where random access is not required. Using this technique, compression and decompression can be done in linear time in the size of the BDD and compression will in many cases reduce the size of the BDD to 1-2 bits per node. Empirical results for our compression technique are presented, including comparisons with previously introduced techniques, showing that the new technique dominate on all tested instances.

A number of compact representation forms that are investigated in the knowledge compilation community are utilized in interactive product configuration and other forms of decision support. Multi-valued decision diagrams (MDDs) are particularly well suited for interactive configuration. However, for large variable domains MDDs can be unnecessarily large if many values are repeating on different edges. In this paper we suggest exploiting the repetitive occurrences of values through the introduction of pseudo-nodes. The technique can be easily applied over MDDs as well as their more succinct counterpart, interval decision diagrams (IDDs). The compactness of the resulting representations, layer-compressed MDDs (lcMDDs) and layer-compressed IDDs (lcIDDs), is demonstrated empirically on artificial and real-world instances.

A well established technology in the knowledge compilation community is the encoding of constraint satisfaction problems (CSPs) by binary decision diagrams (BDDs). A technology that among other things has found its use interactive configuration and other kinds of decision support. The main contribution of this paper is the observation that zero-suppressed binary decision diagrams (ZBDDs)that originally was intended for set-manipulation are very well suited to represent CSPs efficiently. As ZBDDs are already efficiently supported by the popular decision diagram package Cudd [17], no extra implementation is needed in order to use ZBDDs instead of BDDs. Using the real-world CSP instances from CLib [5], we empirically demonstrate that using ZBDDs instead of BDDs often result in significantly smaller representations. We also show that this trend holds as well during the compilation of the decision diagrams, which can make the difference between whether or not a CSP can be compiled, given the amount of RAM available.

A generalization of the problem of interactive configuration has previously been presented in [1]. This generalization utilized decomposition to extend the standard finite domain interactive configuration framework to deal with unbounded string variables and provided features such as prefix auto-completion. In this paper we present several significant improvements to the core data structures and algorithms in [1] as well as the first implementation of an interactive configurator on string variables. The primary improvement is obtained by replacing the binary decomposition model with a finite domain model. We then describe an optimization for this model which allows us to replace the use of costly conjunctions with simple restrict operations during synchronization between decomposed constraints. In addition we describe how to improve the performance of the auto-complete operation, by using projection on relevant variables to significantly reduce the size of the data structures involved. We empirically verify the critical significance of these improvements using our own implementation of a string variable based configurator on real-world example data.

We consider deterministic dictionaries in the parallel disk model, motivated by applications such as file systems. Our main results show that if the number of disks is moderately large (at least logarithmic in the size of the universe from which keys come), performance similar to the expected performance of randomized dictionaries can be achieved. Thus, we may avoid randomization by extending parallelism. We give several algorithms with different performance tradeoffs. One of our main tools is a deterministic load balancing scheme based on expander graphs, that may be of independent interest. Our algorithms assume access to certain expander graphs "for free". While current explicit constructions of expander graphs have suboptimal parameters, we show how to get near-optimal expanders for the case where the amount of data is polynomially related to the size of internal memory.