Online association rule mining

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Online association rule mining

Full text

Pdf (1.18 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1999 ACM SIGMOD international conference on Management of data table of contents

Philadelphia, Pennsylvania, United States

Pages: 145 - 156

Year of Publication: 1999

ISBN:1-58113-084-8

Also published in ...

Author

Christian Hidber

International Computer Science Institute, Berkeley

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 118, Citation Count: 43

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/304182.304195 What is a DOI?

ABSTRACT

We present a novel algorithm to compute large itemsets online. The user is free to change the support threshold any time during the first scan of the transaction sequence. The algorithm maintains a superset of all large itemsets and for each itemset a shrinking, deterministic interval on its support. After at most 2 scans the algorithm terminates with the precise support for each large itemset. Typically our algorithm is by an order of magnitude more memory efficient than Apriori or DIC.

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.

	AIS93	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
	AS94	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
	AY97	Charu C. Aggarwal and Philip S. Yu. Online generation of association rules. Technical Report RC 20899 (92609), IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY, June 1997.
	AY98	Charu C. Aggarwal and Philip S. Yu. Mining large itemsets for association rules. Bulletin of the IEEE Computer Society Technical Comittee on Data Engineering, pages 23-31, March 1998.
	Bay98	Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
	BMUT97	Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
	CHNW96	David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996
	CLK97	David Wai-Lok Cheung , Sau Dan Lee , Ben Kao, A General Incremental Technique for Maintaining Discovered Association Rules, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.185-194, April 01-04, 1997
	Hel96	Joseph M. Hellerstein, The Case for Online Aggregation, University of California at Berkeley, Berkeley, CA, 1996
	HHW97	Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
	Hid98	Christian Hidber, Online Association Rule Mining, University of California at Berkeley, Berkeley, CA, 1998
	SON95	Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
	TBAR97	Shiby Thomas, Sreenath Bodagala, Khaled Alsabti, and Sanjay Ranka. An efficient algorithm for the incremental updation of association rules in large databases. In Proceedings of the 3rd International conference on Knowledge Discovery and Data Mining (KDD 97), New Port Beach, California, August 1997.
	Toi96	Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
	ZPLO96	Mohammed J Zaki , Srinivasan Parthasarathy , Wei Li , Mitsunori Ogihara, Evaluation of Sampling for Data Mining of Association Rules, University of Rochester, Rochester, NY, 1996

CITED BY 43

	Walid G. Aref , Mohamed G. Elfeky , Ahmed K. Elmagarmid, Incremental, Online, and Merge Mining of Partial Periodic Patterns in Time-Series Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.3, p.332-342, March 2004
	Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, Depth first generation of long patterns, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.108-118, August 20-23, 2000, Boston, Massachusetts, United States
	Biswadeep Nag , Prasad M. Deshpande , David J. DeWitt, Using a knowledge cache for interactive discovery of association rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.244-253, August 15-18, 1999, San Diego, California, United States
	Naren Ramakrishnan , Calvin J. Ribbens, Mining and visualizing recommendation spaces for elliptic PDEs with continuous attributes, ACM Transactions on Mathematical Software (TOMS), v.26 n.2, p.254-273, June 2000
	Xindong Wu , Shichao Zhang, Synthesizing High-Frequency Rules from Different Data Sources, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.353-367, February 2003
	Joong Hyuk Chang , Won Suk Lee, estWin: adaptively monitoring the recent change of frequent itemsets over online data streams, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Bin Chen , Peter Haas , Peter Scheuermann, A new two-phase sampling based algorithm for discovering association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Venkatesh Ganti , Raghu Ramakrishnan, Mining and monitoring evolving data, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Naren Ramakrishnan , Calvin J. Ribbens, Mining and visualizing recommendation spaces for PDE solvers: the continuous attributes case, Computational science, mathematics and software, Purdue University Press, West Lafayette, IN, 2002
	Shichao Zhang , Li Liu, Mining dynamic databases by weighting, Acta Cybernetica, v.16 n.1, p.179-205, January 2003
	Joong Hyuk Chang , Won Suk Lee, Finding recent frequent itemsets adaptively over online data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Laks V. S. Lakshmanan , Carson Kai-Sang Leung , Raymond T. Ng, Efficient dynamic mining of constrained frequent sets, ACM Transactions on Database Systems (TODS), v.28 n.4, p.337-389, December 2003
	Amitabha Das , Wee-Keong Ng , Yew-Kwong Woon, Rapid association rule mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas, Interactive Data Analysis: The Control Project, Computer, v.32 n.8, p.51-59, August 1999
	Fernando Berzal , Juan-Carlos Cubero , Daniel Sánchez , José María Serrano, ART: A Hybrid Classification Model, Machine Learning, v.54 n.1, p.67-92, January 2004
	Miroslav Kubat , Alaaeldin Hafez , Vijay V. Raghavan , Jayakrishna R. Lekkala , Wei Kian Chen, Itemset Trees for Targeted Association Querying, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1522-1534, November 2003
	Zahid Hossain , Sk Ahad Ali, Unified descriptive language for association rules in data mining, Second international workshop on Intelligent systems design and application, p.227-232, August 07-08, 2002, Atlanta, Georgia
	Pauray S. M. Tsai , Chien-Ming Chen, Mining interesting association rules from customer databases and transaction databases, Information Systems, v.29 n.8, p.685-696, December 2004
	A Support-Ordered Trie for Fast Frequent Itemset Discovery, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.875-879, July 2004
	Jianyong Wang , Jiawei Han , Ying Lu , Petre Tzvetkov, TFP: An Efficient Algorithm for Mining Top-K Frequent Closed Itemsets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.652-664, May 2005
	Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
	Edward R. Omiecinski, Alternative Interest Measures for Mining Associations in Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.57-69, January 2003
	Joong Hyuk Chang , Won Suk Lee, estWin: Online data stream mining of recent frequent itemsets by sliding window method, Journal of Information Science, v.31 n.2, p.76-90, April 2005
	Tho Manh Nguyen , Josef Schiefer , A. Min Tjoa, Sense & response service architecture (SARESA): an approach towards a real-time business intelligence solution and its use for a fraud detection application, Proceedings of the 8th ACM international workshop on Data warehousing and OLAP, November 04-05, 2005, Bremen, Germany
	Fang Liu , Zhengding Lu , Songfeng Lu, Mining association rules using clustering, Intelligent Data Analysis, v.5 n.4, p.309-326, September 2001
	Thomas Legler , Wolfgang Lehner , Andrew Ross, Data mining with the SAP NetWeaver BI accelerator, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Joong Hyuk Chang , Won Suk Lee, Finding recently frequent itemsets adaptively over online transactional data streams, Information Systems, v.31 n.8, p.849-869, December 2006
	Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
	Shariq J. Rizvi , Jayant R. Haritsa, Maintaining data privacy in association rule mining, Proceedings of the 28th international conference on Very Large Data Bases, p.682-693, August 20-23, 2002, Hong Kong, China
	Flip Korn , S. Muthukrishnan , Divesh Srivastava, Reverse nearest neighbor aggregates over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.814-825, August 20-23, 2002, Hong Kong, China
	Carson Kai-Sang Leung , Quamrul I. Khan , Zhan Li , Tariqul Hoque, CanTree: a canonical-order tree for incremental frequent-pattern mining, Knowledge and Information Systems, v.11 n.3, p.287-311, April 2007
	Laks V. S. Lakshmanan , Carson Kai-Sang Leung , Raymond T. Ng, The segment support map: scalable mining of frequent itemsets, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.21-27, Dec. 2000
	Jochen Hipp , Ulrich Güntzer , Gholamreza Nakhaeizadeh, Algorithms for association rule mining — a general survey and comparison, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.58-64, June, 2000
	Theodore Johnson , Laks V. S. Lakshmanan , Raymond T. Ng, The 3W Model and Algebra for Unified Data Mining, Proceedings of the 26th International Conference on Very Large Data Bases, p.21-32, September 10-14, 2000
	Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007
	Huai Yang , Li Lee , Wynne Hsu, Finding hot query patterns over an XQuery stream, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.318-332, December 2004
	Ming-Yen Lin , Sue-Chen Hsueh , Sheng-Kun Hwang, Interactive mining of frequent itemsets over arbitrary time intervals in a data stream, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Aaron Ceglar , John F. Roddick, GAM: a guidance enabled association mining environment, International Journal of Business Intelligence and Data Mining, v.2 n.1, p.3-28, March 2007
	Tho Manh Nguyen , Josef Schiefer , A. Min Tjoa, ZELESSA: an enabler for real-time sensing, analysing and acting on continuous event streams, International Journal of Business Intelligence and Data Mining, v.2 n.1, p.105-141, March 2007
	Zhibo Chen , Carlos Ordonez, Efficient OLAP with UDFs, Proceeding of the ACM 11th international workshop on Data warehousing and OLAP, October 30-30, 2008, Napa Valley, California, USA
	Mehmet Kaya , Reda Alhajj, Online mining of fuzzy multidimensional weighted association rules, Applied Intelligence, v.29 n.1, p.13-34, August 2008
	Xuan Hong Dang , Wee-Keong Ng , Kok-Leong Ong, Online mining of frequent sets in data streams with error guarantee, Knowledge and Information Systems, v.16 n.2, p.245-258, July 2008
	James Cheng , Yiping Ke , Wilfred Ng, A survey on algorithms for mining frequent itemsets over data streams, Knowledge and Information Systems, v.16 n.1, p.1-27, July 2008