Summarizing Transactional Databases With Overlapped Hyperrectangles

Transactional data are ubiquitous. Several methods, including frequent itemsets mining and co-clustering, have been proposed to analyze transactional databases. In this paper, the authors propose a new research problem to succinctly summarize transactional databases. Solving this problem requires linking the high level structure of the database to a potentially huge number of frequent itemsets. They formulate this problem as a set covering problem using overlapped hyperrectangles (a concept generally regarded as tile according to some existing papers); the authors then prove that this problem and its several variations are NP-hard, and they further reveal its relationship with the compact representation of a directed bipartite graph.