Optimizing STR algorithms with tuple compression

Abstract

Table constraints define an arbitrary constraint explicitly as a set of solutions (tuples) or non-solutions. Thus, space is proportional to number of tuples. Simple Tabular Reduction (STR), which dynamically reduces the table size by maintaining a table of only the valid tuples, has been shown to be efficient for enforcing Generalized Arc Consistency. The Cartesian product representation is another way of having a smaller table by compression. We investigate whether STR and the Cartesian product representation can work hand in hand. Our experiments show the compression-based STR can be faster once the tables compress well. Thus, the benefits of the STR2 and STR3 algorithms respectively are retained while consuming less space. © 2013 Springer-Verlag.