Article

Free access

Online association rule mining

Author:

Christian HidberAuthors Info & Claims

SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data

Pages 145 - 156

https://doi.org/10.1145/304182.304195

Published: 01 June 1999 Publication History

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

[1]

R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proc. of the A CM SIGMOD Conference on Management of Data, pages 207-216, Washington, D.C., May 1993.

Digital Library

[2]

R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. of the 20th Int'l Conf. on Very Large Databases, Santiago, Chile, Sept. 1994.

Digital Library

[3]

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.

[4]

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.

[5]

R.J. Bayardo Jr. Efficiently mining long patterns from databases. In Proc. of the 1998 A CM-SIGMOD International Conference on Management of Data, pages 85-93, Seattle, June 1998.

Digital Library

[6]

Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, and Shalom Tsur. Dynamic itemset counting and implication rules for market basket data. In Proceedings of the A CM SIGMOD International Conferenee on Management of Data, volume 26,2 of SIGMOD Record, pages 255-264, New York, May 13th-15th 1997. ACM Press.

Digital Library

[7]

D. Cheung, J. Han, V. Ng, and C.Y. Wong. Maintenance of discovered association rules in large databases: An incremental updating technique. In Proc. of 1996 Int 'l Conf. on Data Engineerin9 (ICDE'96), New Orleans, Louisiana, USA, Feb. 1996.

Digital Library

[8]

David W. L. Cheung, S.D. Lee, and Benjamin Kao. A general incremental technique for maintaining discovered associa - tion rules. In Proceedings of the Filth International Conference On Database Systems For Advanced Applications, pages 185-194, Melbourne, Australia, March 1997.

Digital Library

[9]

Joseph M. Hellerstein. The case for online aggregation. Technical Report UCB//CSD-96-908, EECS Computer Science Divison, University of California at Berkeley, 1996.

[10]

Josepih M. Hellerstein, Peter J. Haas, and Helen j. Wang. Online aggregation. SIG- MOD '97, 1997.

Digital Library

[11]

C. Hidber. Online Association Rule Mining. Technical Report TR-98-033, International Computer Science Institute, Berkeley, CA, September 1998. an earlier version appeared as technical report UCB//CSD- 98-1004 of the Department of Electrical Engineering and Computer Science, University of California at Berkeley.

[12]

A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. In Proceedings of the Very Large Data Base Conference, September 1995.

Digital Library

[13]

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.

[14]

Hannu Toivonen. Sampling large databases for association rules. In T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, and Nandlal L. Sarda, editors, VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, Mumbai (Bombay), India, September 1996. Morgan Kaufmann.

Digital Library

[15]

Mohammed Javeed Zaki, Srinivasan Parthasarathy, Wei Li, and Mitsunori Ogihara,. Evaluation of sampling for data mining of association rules. Technical Report 617, Computer Science Dept., U. Rochester, May 1996.

Cited By

Yosef ARoth IShnaider EBaranes ASchneider M(2024)Horizontal Learning Approach to Discover Association RulesComputers10.3390/computers1303006213:3(62)Online publication date: 28-Feb-2024
https://doi.org/10.3390/computers13030062
Kamath APrice EWoodruff D(2021)A simple proof of a new set disjointness with applications to data streamsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.37Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.37
Skyrius RSkyrius R(2021)Business Intelligence TechnologiesBusiness Intelligence10.1007/978-3-030-67032-0_7(145-185)Online publication date: 9-Mar-2021
https://doi.org/10.1007/978-3-030-67032-0_7
Show More Cited By

Index Terms

Online association rule mining
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Rapid association rule mining
CIKM '01: Proceedings of the tenth international conference on Information and knowledge management

Association rule mining is a well-researched area where many algorithms have been proposed to improve the speed of mining. In this paper, we propose an innovative algorithm called Rapid Association Rule Mining (RARM) to once again break this speed ...
Association rule mining and quantitative association rule mining among infrequent items
Association rule and quantitative association rule mining among infrequent items
MDM '07: Proceedings of the 8th international workshop on Multimedia data mining: (associated with the ACM SIGKDD 2007)

Association rule mining among frequent items has been extensively studied in data mining research. However, in the recent years, there is an increasing demand of mining the infrequent items (such as rare but expensive items). Since exploring interesting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data

June 1999

604 pages

ISBN:1581130848

DOI:10.1145/304182

Chairmen:
Susan B. Davidson
Univ. of Pennsylvania, Philidelphia
,
Christos Faloutsos
Carnegie Mellon Univ., Pittsburgh

ACM SIGMOD Record Volume 28, Issue 2
June 1999
599 pages
ISSN:0163-5808
DOI:10.1145/304181
Chairmen:
Susan Davidson
Univ. of Pennsylvania
,
Christos Faloutsos
Carnegie Mellon Univ.
Issue’s Table of Contents

Copyright © 1999 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS99

Sponsor:

SIGMOD/PODS99: International Conference on Management of Data and Symposium on Principles of Database Systems

May 31 - June 3, 1999

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

146
Total Citations
View Citations
2,270
Total Downloads

Downloads (Last 12 months)108
Downloads (Last 6 weeks)25

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yosef ARoth IShnaider EBaranes ASchneider M(2024)Horizontal Learning Approach to Discover Association RulesComputers10.3390/computers1303006213:3(62)Online publication date: 28-Feb-2024
https://doi.org/10.3390/computers13030062
Kamath APrice EWoodruff D(2021)A simple proof of a new set disjointness with applications to data streamsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.37Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.37
Skyrius RSkyrius R(2021)Business Intelligence TechnologiesBusiness Intelligence10.1007/978-3-030-67032-0_7(145-185)Online publication date: 9-Mar-2021
https://doi.org/10.1007/978-3-030-67032-0_7
Abdel-Basset MMohamed MSmarandache FChang V(2018)Neutrosophic Association Rule Mining Algorithm for Big Data AnalysisSymmetry10.3390/sym1004010610:4(106)Online publication date: 11-Apr-2018
https://doi.org/10.3390/sym10040106
Bhattacharyya ADey PWoodruff D(2018)An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related ProblemsACM Transactions on Algorithms10.1145/326442715:1(1-27)Online publication date: 22-Oct-2018
https://dl.acm.org/doi/10.1145/3264427
Kumar PSingh A(2018)Efficient Generation of Association Rules from Numeric Data Using Genetic Algorithm for Smart CitiesSecurity in Smart Cities: Models, Applications, and Challenges10.1007/978-3-030-01560-2_14(323-343)Online publication date: 5-Nov-2018
https://doi.org/10.1007/978-3-030-01560-2_14
Gawwad MAhmed MFayek M(2017)Frequent Itemset Mining for Big Data Using Greatest Common Divisor TechniqueData Science Journal10.5334/dsj-2017-02516Online publication date: 18-May-2017
https://doi.org/10.5334/dsj-2017-025
Lynden SAkerkar RCuzzocrea ACao JHacid M(2017)Analysis of semantic URLs to support automated linking of structured data on the webProceedings of the 7th International Conference on Web Intelligence, Mining and Semantics10.1145/3102254.3102265(1-6)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3102254.3102265
Guerrero JGarca APersonal ELuque JLen C(2017)Heterogeneous data source integration for smart grid ecosystems based on metadata miningExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.03.00779:C(254-268)Online publication date: 15-Aug-2017
https://dl.acm.org/doi/10.1016/j.eswa.2017.03.007
Liu HHe GJiao WWang GPeng YCheng B(2017)Sequential pattern mining of land cover dynamics based on time-series remote sensing imagesMultimedia Tools and Applications10.1007/s11042-016-3730-676:21(22919-22942)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s11042-016-3730-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents