Succinct summarization of transactional databases: an overlapped hyperrectangle scheme

ABSTRACT

Transactional data are ubiquitous. Several methods, including frequent itemsets mining and co-clustering, have been proposed to analyze transactional databases. In this work, we 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. We formulate this problem as a set covering problem using overlapped hyperrectangles; we then prove that this problem and its several variations are NP-hard. We develop an approximation algorithm HYPER which can achieve a ln(k) + 1 approximation ratio in polynomial time. We propose a pruning strategy that can significantly speed up the processing of our algorithm. Additionally, we propose an efficient algorithm to further summarize the set of hyperrectangles by allowing false positive conditions. A detailed study using both real and synthetic datasets shows the effectiveness and efficiency of our approaches in summarizing transactional databases.

REFERENCES

• 1: Foto Afrati , Aristides Gionis , Heikki Mannila, Approximating a collection of frequent sets, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014057]
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 4: Christan Borgelt. Apriori implementation. http://fuzzy.cs.Uni-Magdeburg.de/ borgelt/Software. Version 4.08.
• 5: Varun Chandola , Vipin Kumar, Summarization – compressing data into an informative representation, Knowledge and Information Systems, v.12 n.3, p.355-378, August 2007 [doi>10.1007/s10115-006-0039-1]
• 6: V. Chvátal. A greedy heuristic for the set-covering problem. Math. Oper. Res, 4:233--235, 1979.
• 7: Christos Faloutsos , Vasileios Megalooikonomou, On data mining, compression, and Kolmogorov complexity, Data Mining and Knowledge Discovery, v.15 n.1, p.3-20, August 2007 [doi>10.1007/s10618-006-0057-3]
• 8: Byron J. Gao , Martin Ester, Turning Clusters into Patterns: Rectangle-Based Discriminative Data Description, Proceedings of the Sixth International Conference on Data Mining, p.200-211, December 18-22, 2006 [doi>10.1109/ICDM.2006.163]
• 9: David Johnson , Shankar Krishnan , Jatin Chhugani , Subodh Kumar , Suresh Venkatasubramanian, Compressing large boolean matrices using reordering techniques, Proceedings of the Thirtieth international conference on Very large data bases, p.13-23, August 31-September 03, 2004, Toronto, Canada
• 10: D. Pisinger Kellerer, Hans; U. Pferschy. Knapsack Problems. Springer Verlag, 2005.
• 11: Laks V. S. Lakshmanan , Raymond T. Ng , Christine Xing Wang , Xiaodong Zhou , Theodore J. Johnson, The generalized MDL approach for summarization, Proceedings of the 28th international conference on Very Large Data Bases, p.766-777, August 20-23, 2002, Hong Kong, China
• 12: Tao Li, A general model for clustering binary data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081894]
• 13: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 14: Jian Pei , Guozhu Dong , Wei Zou , Jiawei Han, Mining condensed frequent-pattern bases, Knowledge and Information Systems, v.6 n.5, p.570-594, September 2004 [doi>10.1007/s10115-003-0133-6]
• 15: Arno Siebes, Jilles Vreeken, and Matthijs van Leeuwen. Item sets that compress. In SDM, 2006.
• 16: Michael Steinbach , Pang-Ning Tan , Vipin Kumar, Support envelopes: a technique for exploring the structure of association patterns, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014086]
• 17: Matthijs van Leeuwen, Jilles Vreeken, and Arno Siebes. Compression picks item sets that matter. In PKDD, pages 585--592, 2006.
• 18: Jilles Vreeken , Matthijs van Leeuwen , Arno Siebes, Characterising the difference, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281274]
• 19: Jianyong Wang , George Karypis, On efficiently summarizing categorical databases, Knowledge and Information Systems, v.9 n.1, p.19-37, January 2006 [doi>10.1007/s10115-005-0216-7]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Theory

Keywords:
hyperrectangle, set cover, summarization, transactional databases