Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Online Association Rule Mining

Christian Hidber

  View Paper (PDF)  

Return to Data Mining - Association Rules and Decision Trees

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: References link to DBLP on the Web.

[AIS93]
Rakesh Agrawal , Tomasz Imielinski , Arun N. Swami : Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993 : 207-216
[AS94]
Rakesh Agrawal , Ramakrishnan Srikant : Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994 : 487-499
[AY97]
Charu C. Aggarwal , Philip S. Yu : Online Generation of Association Rules. ICDE 1998 : 402-411
[AY98]
Charu C. Aggarwal , Philip S. Yu : Mining Large Itemsets for Association Rules. Data Engineering Bulletin 21(1) : 23-31(1998)
[Bay98]
Roberto J. Bayardo Jr. : Efficiently Mining Long Patterns from Databases. SIGMOD Conference 1998 : 85-93
[BMUT97]
Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur : Dynamic Itemset Counting and Implication Rules for Market Basket Data. SIGMOD Conference 1997 : 255-264
[CHNW996]
David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong : Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique. ICDE 1996 : 106-114
[CLK97]
David Wai-Lok Cheung , Sau Dan Lee , Ben Kao : A General Incremental Technique for Maintaining Discovered Association Rules. DASFAA 1997 : 185-194
[Hel96]
...
[HHW97]
Joseph M. Hellerstein , Peter J. Haas , Helen Wang : Online Aggregation. SIGMOD Conference 1997 : 171-182
[Hid98]
...
[SON95]
Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe : An Efficient Algorithm for Mining Association Rules in Large Databases. VLDB 1995 : 432-444
[TBAR97]
Shiby Thomas , Sreenath Bodagala , Khaled Alsabti , Sanjay Ranka : An Efficient Algorithm for the Incremental Updation of Association Rules in Large Databases. KDD 1997 : 263-266
[Toi96]
Hannu Toivonen : Sampling Large Databases for Association Rules. VLDB 1996 : 134-145
[ZPLO96]
Mohammed Javeed Zaki , Srinivasan Parthasarathy , Wei Li , Mitsunori Ogihara : Evaluation of Sampling for Data Mining of Association Rules. RIDE 1997 : 0-

Referenced by

  1. Peter J. Haas : Techniques for Online Exploration of Large Object-Relational Datasets. SSDBM 1999 : 4-12

BIBTEX

@inproceedings{DBLP:conf/sigmod/Hidber99,
  author    = {Christian Hidber},
   editor    = {Alex Delis and
                Christos Faloutsos and
                Shahram Ghandeharizadeh},
   title     = {Online Association Rule Mining},
   booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
                on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,
                USA},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-084-8},
   pages     = {145-156},
   crossref  = {DBLP:conf/sigmod/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM