An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous 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, constraints can be very voluminous and their size can grow exponentially with their arity. To reduce space and the time complexity, researchers have focused on various forms of compression. In this paper we propose a new approach based on maximal frequent itemsets technique and area measure for enumerating the maximal frequent itemsets relevant for compressing table constraints. Our experimental results show the effectiveness and efficiency of this approach on compression and on solving compressed table constraints.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace
The monotone duality problem is defined as follows: Given two monotone formulas f and g in iredundant DNF, decide whether f and g are dual. This problem is the same as duality testing for hypergraphs, that is, checking w…
Problem DecompositionComputational Complexity of Three Central Problems in Itemset Mining
Itemset mining is one of the most studied tasks in knowledge discovery. In this paper we analyze the computational complexity of three central itemset mining problems. We prove that mining confident rules with a given it…
Maximum Entropy Based Significance of Itemsets
We consider the problem of defining the significance of an itemset. We say that the itemset is significant if we are surprised by its frequency when compared to the frequencies of its sub-itemsets. In other words, we est…
A Bayesian Network Model for Interesting Itemsets
Mining itemsets that are the most interesting under a statistical model of the underlying data is a commonly used and well-studied technique for exploratory data analysis, with the most recent interestingness models exhi…
modelFinding Robust Itemsets Under Subsampling
Mining frequent patterns is plagued by the problem of pattern explosion making pattern reduction techniques a key challenge in pattern mining. In this paper we propose a novel theoretical framework for pattern reduction.…