Exploring constraints to efficiently mine emerging patterns from large high-dimensional datasets

Emerging patterns (EPs) were proposed recently to capture changes or differences between datasets: an EP is a multivariate feature whose support increases sharply from a background dataset to a target dataset, and the support ratio is called its growth rate. Interesting long EPs often have low support; mining such EPs from high-dimensional datasets is a great challenge due to the combinatorial explosion of the number of candidates. We propose a Constraint-based EP Miner, ConsEPMiner, that utilizes two types of constraints for effectively pruning the search space: External constraints are user-given minimums on support, growth rate, and growth-rate improvement to con ne the resulting EP set. Inherent constraints -- same subset support, top growth rate, and same origin -- are derived from the properties of EPs and datasets, and are solely for pruning the search space and saving computation. ConsEPMiner can efficiently mine all EPs at low support on large high-dimensional datasets, with low minim...