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 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.