New Methods for Compressing Table Constraints

Constraint Programming is a powerful paradigm to model and solve combinatorial problems. While there are many kinds of constraints, the table constraint is perhaps the most significant—being the most well-studied and has the ability to encode any other constraints defined on finite variables. However, these constraints admit practical boundaries because of the memory space required to represent them which may grow exponentially with their arity. To reduce space complexity, researchers have focused on various forms of compression. In this paper we propose two approaches for compressing table constraints. The first one called FPTCM+ (FP-Tree Compression Method+) is an improvement of an existing method, it exploits the compression rate metric instead of the savings that can be offered by an itemset to enumerate the frequent itemsets relevant for compression. The second approach, called IFPTCM+, is an improvement of FPTCM+ such that it exploits the top-k approach mining method to dynamically choose the value of the minimum threshold Smin. This allows higher compression rate with lesser frequent itemsets by identifying only the more frequent itemsets relevant for compression. Experimental results show the effectiveness and efficiency of our approaches.