Approximating a collection of frequent sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating a collection of frequent sets

Full text

Pdf (221 KB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Seattle, WA, USA

SESSION: Research track papers table of contents

Pages: 12 - 19

Year of Publication: 2004

ISBN:1-58113-888-1

Authors

Foto Afrati	University of Athens, Greece
Aristides Gionis	University of Helsinki, Finland
Heikki Mannila	University of Helsinki, Finland

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data
SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 103, Citation Count: 21

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1014052.1014057 What is a DOI?

ABSTRACT

One of the most well-studied problems in data mining is computing the collection of frequent item sets in large transactional databases. One obstacle for the applicability of frequent-set mining is that the size of the output collection can be far too large to be carefully examined and understood by the users. Even restricting the output to the border of the frequent item-set collection does not help much in alleviating the problem.In this paper we address the issue of overwhelmingly large output size by introducing and studying the following problem: What are the k sets that best approximate a collection of frequent item sets? Our measure of approximating a collection of sets by k sets is defined to be the size of the collection covered by the the k sets, i.e., the part of the collection that is included in one of the k sets. We also specify a bound on the number of extra sets that are allowed to be covered. We examine different problem variants for which we demonstrate the hardness of the corresponding problems and we provide simple polynomial-time approximation algorithms. We give empirical evidence showing that the approximation methods work well in practice.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
	2	Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
	3	Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
	4	Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
	5	William Feller. An introduction to probability theory and its applications. John Wiley & Sons, 1968.
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	Bart Goethals. Frequent itemset mining implementations. http://www.cs.helsinki.fi/u/goethals/software/.
	8	Jiawei Han , Jianyong Wang , Ying Lu , Petre Tzvetkov, Mining Top.K Frequent Closed Patterns without Minimum Support, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.211, December 09-12, 2002
	9	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	10	Ron Kohavi , Carla E. Brodley , Brian Frasca , Llew Mason , Zijian Zheng, KDD-Cup 2000 organizers' report: peeling the onion, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.86-93, Dec. 2000 [doi>10.1145/380995.381033]
	11	Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
	12	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	13	Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
	14	Jian Pei , Guozhu Dong , Wei Zou , Jiawei Han, On Computing Condensed Frequent Pattern Bases, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.378, December 09-12, 2002

CITED BY 21

	Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Xifeng Yan , Hong Cheng , Jiawei Han , Dong Xin, Summarizing itemset patterns: a profile-based approach, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Qiaozhu Mei , Dong Xin , Hong Cheng , Jiawei Han , ChengXiang Zhai, Generating semantic annotations for frequent patterns with context analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Fabian Mörchen , Alfred Ultsch, Efficient mining of understandable patterns from multivariate interval time series, Data Mining and Knowledge Discovery, v.15 n.2, p.181-215, October 2007
	Dong Xin , Hong Cheng , Xifeng Yan , Jiawei Han, Extracting redundancy-aware top-k patterns, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Chao Wang , Srinivasan Parthasarathy, Summarizing itemset patterns using probabilistic models, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, On compressing frequent patterns, Data & Knowledge Engineering, v.60 n.1, p.5-29, January, 2007
	Lei Chang , Tengjiao Wang , Dongqing Yang , Hua Luan , Shiwei Tang, Efficient algorithms for incremental maintenance of closed sequential patterns in large databases, Data & Knowledge Engineering, v.68 n.1, p.68-106, January, 2009
	Qiaozhu Mei , Dong Xin , Hong Cheng , Jiawei Han , Chengxiang Zhai, Semantic annotation of frequent patterns, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.3, p.11-es, December 2007
	Toon Calders, Itemset frequency satisfiability: Complexity and axiomatization, Theoretical Computer Science, v.394 n.1-2, p.84-111, March, 2008
	Junsong Yuan , Ying Wu , Ming Yang, From frequent itemsets to semantically meaningful visual patterns, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Byron J. Gao , Martin Ester , Jin-Yi Cai , Oliver Schulte , Hui Xiong, The minimum consistent subset cover problem and its applications in data mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Kun-Ta Chuang , Jiun-Long Huang , Ming-Syan Chen, Mining top-k frequent patterns in the presence of the memory constraint, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1321-1344, August 2008
	Pauli Miettinen, On the Positive--Negative Partial Set Cover problem, Information Processing Letters, v.108 n.4, p.219-221, October, 2008
	Yang Xiang , Ruoming Jin , David Fuhry , Feodor F. Dragan, Succinct summarization of transactional databases: an overlapped hyperrectangle scheme, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Ruoming Jin , Muad Abu-Ata , Yang Xiang , Ning Ruan, Effective and efficient itemset pattern summarization: regression-based approaches, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Fabien De Marchi , Stéphane Lopes , Jean-Marc Petit, Unary and n-ary inclusion dependency discovery in relational databases, Journal of Intelligent Information Systems, v.32 n.1, p.53-73, February 2009
	Haifeng Li , Hong Chen, Mining non-derivable frequent itemsets over data stream, Data & Knowledge Engineering, v.68 n.5, p.481-498, May, 2009
	Ardian Kristanto Poernomo , Vivekanand Gopalkrishnan, CP-summary: a concise representation for browsing frequent itemsets, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Varun Chandola , Vipin Kumar, Summarization – compressing data into an informative representation, Knowledge and Information Systems, v.12 n.3, p.355-378, August 2007
	Ruoming Jin , Yang Xiang , Lin Liu, Cartesian contour: a concise representation for a collection of frequent sets, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France