ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Mining Association Rules between Sets of Items in Large Databases.

Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993: 207-216
@inproceedings{DBLP:conf/sigmod/AgrawalIS93,
  author    = {Rakesh Agrawal and
               Tomasz Imielinski and
               Arun N. Swami},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Mining Association Rules between Sets of Items in Large Databases},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {207-216},
  ee        = {http://doi.acm.org/10.1145/170035.170072, db/conf/sigmod/AgrawalIS93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We are given a large database of customer transactions. Each transaction consists of items purchased by a customer in a visit. We present an efficient algorithm that generates all significant association rules between items in the database. The algorithm incorporates buffer management and novel estimation and pruning techniques. We also present results of applying this algorithm to sales data obtained from a large retailing company, which shows the effectiveness of the algorithm.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1050 KB]

References

[1]
Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Database Mining: A Performance Perspective. IEEE Trans. Knowl. Data Eng. 5(6): 914-925(1993) BibTeX
[2]
Rakesh Agrawal, Sakti P. Ghosh, Tomasz Imielinski, Balakrishna R. Iyer, Arun N. Swami: An Interval Classifier for Database Mining Applications. VLDB 1992: 560-573 BibTeX
[3]
...
[4]
...
[5]
...
[6]
Mieczyslaw M. Kokar: Discovering Functional Formulas through Changing Representation Base. AAAI 1986: 455-459 BibTeX
[7]
...
[8]
Heikki Mannila, Kari-Jouko Räihä: Dependency Inference. VLDB 1987: 155-158 BibTeX
[9]
J. Ross Quinlan: Induction of Decision Trees. Machine Learning 1(1): 81-106(1986) BibTeX
[10]
Gregory Piatetsky-Shapiro: Discovery, Analysis, and Presentation of Strong Rules. Knowledge Discovery in Databases 1991: 229-248 BibTeX
[11]
Gregory Piatetsky-Shapiro, William J. Frawley (Eds.): Knowledge Discovery in Databases. AAAI/MIT Press 1991, ISBN 0-262-62080-4
Contents BibTeX
[12]
Leslie G. Valiant: A Theory of the Learnable. Commun. ACM 27(11): 1134-1142(1984) BibTeX
[13]
Leslie G. Valiant: Learning Disjunction of Conjunctions. IJCAI 1985: 560-566 BibTeX
[14]
...

Referenced by

  1. Jeff Edmonds, Jarek Gryz, Dongming Liang, Renée J. Miller: Mining for Empty Rectangles in Large Data Sets. ICDT 2001: 174-188
  2. Toon Calders, Jan Paredaens: Axiomatization of Frequent Sets. ICDT 2001: 204-218
  3. Flip Korn, Alexandros Labrinidis, Yannis Kotidis, Christos Faloutsos: Quantifiable Data Mining Using Ratio Rules. VLDB J. 8(3-4): 254-266(2000)
  4. Edwin M. Knorr, Raymond T. Ng, V. Tucakov: Distance-Based Outliers: Algorithms and Applications. VLDB J. 8(3-4): 237-253(2000)
  5. David Gibson, Jon M. Kleinberg, Prabhakar Raghavan: Clustering Categorical Data: An Approach Based on Dynamical Systems. VLDB J. 8(3-4): 222-236(2000)
  6. Themistoklis Palpanas: Knowledge Discovery in Data Warehouses. SIGMOD Record 29(3): 88-100(2000)
  7. Ke Wang, Yu He, Jiawei Han: Mining Frequent Itemsets Using Support Constraints. VLDB 2000: 43-52
  8. Theodore Johnson, Laks V. S. Lakshmanan, Raymond T. Ng: The 3W Model and Algebra for Unified Data Mining. VLDB 2000: 21-32
  9. Pradeep Shenoy, Jayant R. Haritsa, S. Sudarshan, Gaurav Bhalotia, Mayank Bawa, Devavrat Shah: Turbo-charging Vertical Mining of Large Databases. SIGMOD Conference 2000: 22-33
  10. Shinichi Morishita, Jun Sese: Traversing Itemset Lattice with Statistical Metric Pruning. PODS 2000: 226-236
  11. Fabrizio Angiulli, Rachel Ben-Eliyahu-Zohary, Giovambattista Ianni, Luigi Palopoli: Computational Properties of Metaquerying Problems. PODS 2000: 237-244
  12. Philip S. Yu: Review - Mining Association Rules between Sets of Items in Large Databases. ACM SIGMOD Digital Review 1: (1999)
  13. Sophie Cluet: Review - Mining Association Rules between Sets of Items in Large Databases. ACM SIGMOD Digital Review 1: (1999)
  14. Minos N. Garofalakis, Rajeev Rastogi, S. Seshadri, Kyuseok Shim: Data Mining and the Web: Past, Present and Future. Workshop on Web Information and Data Management 1999: 43-47
  15. Ke Wang, Senqiang Zhou, Shiang Chen Liew: Building Hierarchical Classifiers Using Class Proximity. VLDB 1999: 363-374
  16. Edwin M. Knorr, Raymond T. Ng: Finding Intensional Knowledge of Distance-Based Outliers. VLDB 1999: 211-222
  17. H. V. Jagadish, J. Madar, Raymond T. Ng: Semantic Compression and Pattern Extraction with Fascicles. VLDB 1999: 186-198
  18. Wen-Chi Hou: A Framework for Statistical Data Mining with Summary Tables. SSDBM 1999: 14-23
  19. Raymond T. Ng, Laks V. S. Lakshmanan, Jiawei Han, Teresa Mah: Exploratory Mining via Constrained Frequent Set Queries. SIGMOD Conference 1999: 556-558
  20. Laks V. S. Lakshmanan, Raymond T. Ng, Jiawei Han, Alex Pang: Optimization of Constrained Frequent Set Queries with 2-variable Constraints. SIGMOD Conference 1999: 157-168
  21. Christian Hidber: Online Association Rule Mining. SIGMOD Conference 1999: 145-156
  22. Alin Deutsch, Mary F. Fernández, Dan Suciu: Storing Semistructured Data with STORED. SIGMOD Conference 1999: 431-442
  23. Charu C. Aggarwal, Joel L. Wolf, Philip S. Yu: A New Method for Similarity Indexing of Market Basket Data. SIGMOD Conference 1999: 407-418
  24. Nicolas Pasquier, Yves Bastide, Rafik Taouil, Lotfi Lakhal: Discovering Frequent Closed Itemsets for Association Rules. ICDT 1999: 398-416
  25. Rajeev Rastogi, Kyuseok Shim: Mining Optimized Support Rules for Numeric Attributes. ICDE 1999: 206-215
  26. Brian Dunkel, Nandit Soparkar: Data Organization and Access for Efficient Data Mining. ICDE 1999: 522-529
  27. Roberto J. Bayardo Jr., Rakesh Agrawal, Dimitrios Gunopulos: Constraint-Based Rule Mining in Large, Dense Databases. ICDE 1999: 188-197
  28. Jean-François Boulicaut, Patrick Marcel, Christophe Rigotti: Query Driven Knowledge Discovery in Multidimensional Data. DOLAP 1999: 87-93
  29. Philip S. Yu: Data Mining and Personalization Technologies. DASFAA 1999: 6-13
  30. Suh-Ying Wur, Yungho Leu: An Effective Boolean Algorithm for Mining Association Rules in Large Databases. DASFAA 1999: 179-186
  31. Marek Wojciechowski: Mining Various Patterns in Sequential Data in an SQL-like Manner. ADBIS (Short Papers) 1999: 131-138
  32. Holger Günzel, Jens Albrecht, Wolfgang Lehner: Data Mining in a Multidimensional Environment. ADBIS 1999: 191-204
  33. Ming-Syan Chen, Jong Soo Park, Philip S. Yu: Efficient Data Mining for Path Traversal Patterns. IEEE Trans. Knowl. Data Eng. 10(2): 209-221(1998)
  34. Richard T. Snodgrass, Laura M. Haas, Alberto O. Mendelzon, Z. Meral Özsoyoglu, Jan Paredaens, Krithi Ramamritham, Nick Roussopoulos, Jennifer Widom, Philip S. Yu: Reminiscences on Influential Papers. SIGMOD Record 27(4): 81-85(1998)
  35. Chan Man Kuok, Ada Wai-Chee Fu, Man Hon Wong: Mining Fuzzy Association Rules in Databases. SIGMOD Record 27(1): 41-46(1998)
  36. G. D. Ramkumar, Arun N. Swami: Clustering Data Without Distance Functions. IEEE Data Eng. Bull. 21(1): 9-14(1998)
  37. Charu C. Aggarwal, Philip S. Yu: Mining Large Itemsets for Association Rules. IEEE Data Eng. Bull. 21(1): 23-31(1998)
  38. Craig Silverstein, Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman: Scalable Techniques for Mining Causal Structures. VLDB 1998: 594-605
  39. Sridhar Ramaswamy, Sameer Mahajan, Abraham Silberschatz: On the Discovery of Interesting Patterns in Association Rules. VLDB 1998: 368-379
  40. Yasuhiko Morimoto, Takeshi Fukuda, Hirofumi Matsuzawa, Takeshi Tokuyama, Kunikazu Yoda: Algorithms for Mining Association Rules for Binary Segmentations of Huge Categorical Databases. VLDB 1998: 380-391
  41. Flip Korn, Alexandros Labrinidis, Yannis Kotidis, Christos Faloutsos: Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining. VLDB 1998: 582-593
  42. Edwin M. Knorr, Raymond T. Ng: Algorithms for Mining Distance-Based Outliers in Large Datasets. VLDB 1998: 392-403
  43. David Gibson, Jon M. Kleinberg, Prabhakar Raghavan: Clustering Categorical Data: An Approach Based on Dynamical Systems. VLDB 1998: 311-322
  44. Shalom Tsur, Jeffrey D. Ullman, Serge Abiteboul, Chris Clifton, Rajeev Motwani, Svetlozar Nestorov, Arnon Rosenthal: Query Flocks: A Generalization of Association-Rule Mining. SIGMOD Conference 1998: 1-12
  45. Sunita Sarawagi, Shiby Thomas, Rakesh Agrawal: Integrating Mining with Relational Database Systems: Alternatives and Implications. SIGMOD Conference 1998: 343-354
  46. Raymond T. Ng, Laks V. S. Lakshmanan, Jiawei Han, Alex Pang: Exploratory Mining and Pruning Optimizations of Constrained Association Rules. SIGMOD Conference 1998: 13-24
  47. Roberto J. Bayardo Jr.: Efficiently Mining Long Patterns from Databases. SIGMOD Conference 1998: 85-93
  48. Charu C. Aggarwal, Philip S. Yu: A New Framework For Itemset Generation. PODS 1998: 18-24
  49. Ashok Savasere, Edward Omiecinski, Shamkant B. Navathe: Mining for Strong Negative Associations in a Large Database of Customer Transactions. ICDE 1998: 494-502
  50. Rajeev Rastogi, Kyuseok Shim: Mining Optimized Association Rules with Categorical and Numeric Attributes. ICDE 1998: 503-512
  51. Banu Özden, Sridhar Ramaswamy, Abraham Silberschatz: Cyclic Association Rules. ICDE 1998: 412-421
  52. Rosa Meo, Giuseppe Psaila, Stefano Ceri: A Tightly-Coupled Architecture for Data Mining. ICDE 1998: 316-323
  53. Jun-Lin Lin, Margaret H. Dunham: Mining Association Rules: Anti-Skew Algorithms. ICDE 1998: 486-493
  54. Charu C. Aggarwal, Philip S. Yu: Online Generation of Association Rules. ICDE 1998: 402-411
  55. Chien-Le Goh, Masahiko Tsukamoto, Shojiro Nishio: Fast Methods with Magic Sampling for Knowledge Discovery in Deductive Databases with Large Deduction Results. ER Workshops 1998: 14-28
  56. Cecil Chua Eng Huang, Roger H. L. Chiang, Ee-Peng Lim: A Heuristic Method for Correlating Attribute Group Pairs in Data Mining. ER Workshops 1998: 29-40
  57. Dao-I Lin, Zvi M. Kedem: Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set. EDBT 1998: 105-119
  58. Ling Feng, Hongjun Lu, Y. C. Tay, Anthony K. H. Tung: Buffer Management in Distributed Database Systems: A Data Mining Based Approach. EDBT 1998: 246-260
  59. Marek Wojciechowski, Maciej Zakrzewicz: Itemset Materializing for Fast Mining of Association Rules. ADBIS 1998: 284-295
  60. Tomasz Imielinski, Aashu Virmani: Association Rules... and What's Next? Towards Second Generation Data Mining Systems. ADBIS 1998: 6-25
  61. Jong Soo Park, Ming-Syan Chen, Philip S. Yu: Using a Hash-Based Method with Transaction Trimming for Mining Association Rules. IEEE Trans. Knowl. Data Eng. 9(5): 813-825(1997)
  62. Yasuhiko Morimoto, Hiromu Ishii, Shinichi Morishita: Efficient Construction of Regression Trees with Range and Region Splitting. VLDB 1997: 166-175
  63. Khaled Alsabti, Sanjay Ranka, Vineet Singh: A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data. VLDB 1997: 346-355
  64. Renée J. Miller, Yuping Yang: Association Rules over Interval Data. SIGMOD Conference 1997: 452-461
  65. Eui-Hong Han, George Karypis, Vipin Kumar: Scalable Parallel Data Mining for Association Rules. SIGMOD Conference 1997: 277-288
  66. Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, Shalom Tsur: Dynamic Itemset Counting and Implication Rules for Market Basket Data. SIGMOD Conference 1997: 255-264
  67. Sergey Brin, Rajeev Motwani, Craig Silverstein: Beyond Market Baskets: Generalizing Association Rules to Correlations. SIGMOD Conference 1997: 265-276
  68. Roberto J. Bayardo Jr., William Bohrer, Richard S. Brice, Andrzej Cichocki, Jerry Fowler, Abdelsalam Helal, Vipul Kashyap, Tomasz Ksiezyk, Gale Martin, Marian H. Nodine, Mosfeq Rashid, Marek Rusinkiewicz, Ray Shea, C. Unnikrishnan, Amy Unruh, Darrell Woelk: InfoSleuth: Semantic Integration of Information in Open and Dynamic Environments (Experience Paper). SIGMOD Conference 1997: 195-206
  69. Dimitrios Gunopulos, Roni Khardon, Heikki Mannila, Hannu Toivonen: Data mining, Hypergraph Transversals, and Machine Learning. PODS 1997: 209-216
  70. Heikki Mannila: Methods and Problems in Data Mining. ICDT 1997: 41-55
  71. Dimitrios Gunopulos, Heikki Mannila, Sanjeev Saluja: Discovering All Most Specific Sentences by Randomized Algorithms. ICDT 1997: 215-229
  72. Brian Lent, Arun N. Swami, Jennifer Widom: Clustering Association Rules. ICDE 1997: 220-231
  73. David Wai-Lok Cheung, Sau Dan Lee, Ben Kao: A General Incremental Technique for Maintaining Discovered Association Rules. DASFAA 1997: 185-194
  74. Tadeusz Morzy, Maciej Zakrzewicz: SQL-Like Language for Database Mining. ADBIS 1997: 311-317
  75. Abraham Silberschatz, Alexander Tuzhilin: What Makes Patterns Interesting in Knowledge Discovery Systems. IEEE Trans. Knowl. Data Eng. 8(6): 970-974(1996)
  76. Edwin M. Knorr, Raymond T. Ng: Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining. IEEE Trans. Knowl. Data Eng. 8(6): 884-897(1996)
  77. Wen-Chi Hou: Extraction and Applications of Statistical Relationships in Relational Databases. IEEE Trans. Knowl. Data Eng. 8(6): 939-945(1996)
  78. Jiawei Han, Yue Huang, Nick Cercone, Yongjian Fu: Intelligent Query Answering by Knowledge Discovery Techniques. IEEE Trans. Knowl. Data Eng. 8(3): 373-390(1996)
  79. David Wai-Lok Cheung, Vincent T. Y. Ng, Ada Wai-Chee Fu, Yongjian Fu: Efficient Mining of Association Rules in Distributed Databases. IEEE Trans. Knowl. Data Eng. 8(6): 911-922(1996)
  80. Ming-Syan Chen, Jiawei Han, Philip S. Yu: Data Mining: An Overview from a Database Perspective. IEEE Trans. Knowl. Data Eng. 8(6): 866-883(1996)
  81. Rakesh Agrawal, John C. Shafer: Parallel Mining of Association Rules. IEEE Trans. Knowl. Data Eng. 8(6): 962-969(1996)
  82. Tomasz Imielinski, Heikki Mannila: A Database Perspective on Knowledge Discovery. Commun. ACM 39(11): 58-64(1996)
  83. Marisa S. Viveros, John P. Nearhos, Michael J. Rothman: Applying Data Mining Techniques to a Health Insurance Information System. VLDB 1996: 286-294
  84. Hannu Toivonen: Sampling Large Databases for Association Rules. VLDB 1996: 134-145
  85. Rosa Meo, Giuseppe Psaila, Stefano Ceri: A New SQL-like Operator for Mining Association Rules. VLDB 1996: 122-133
  86. Heikki Mannila: Data Mining: Machine Learning, Statistics, and Databases. SSDBM 1996: 2-9
  87. Ramakrishnan Srikant, Rakesh Agrawal: Mining Quantitative Association Rules in Large Relational Tables. SIGMOD Conference 1996: 1-12
  88. Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Data Mining Using Two-Dimensional Optimized Accociation Rules: Scheme, Algorithms, and Visualization. SIGMOD Conference 1996: 13-23
  89. Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Mining Optimized Association Rules for Numeric Attributes. PODS 1996: 182-191
  90. David Wai-Lok Cheung, Jiawei Han, Vincent T. Y. Ng, C. Y. Wong: Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique. ICDE 1996: 106-114
  91. Ramakrishnan Srikant, Rakesh Agrawal: Mining Sequential Patterns: Generalizations and Performance Improvements. EDBT 1996: 3-17
  92. Ramakrishnan Srikant, Rakesh Agrawal: Mining Generalized Association Rules. VLDB 1995: 407-419
  93. Ashok Savasere, Edward Omiecinski, Shamkant B. Navathe: An Efficient Algorithm for Mining Association Rules in Large Databases. VLDB 1995: 432-444
  94. Jiawei Han, Yongjian Fu: Discovery of Multiple-Level Association Rules from Large Databases. VLDB 1995: 420-431
  95. Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310
  96. Jong Soo Park, Ming-Syan Chen, Philip S. Yu: An Effective Hash Based Algorithm for Mining Association Rules. SIGMOD Conference 1995: 175-186
  97. Wen-Chi Hou, Zhongyang Zhang: Enhancing Database Correctness: a Statistical Approach. SIGMOD Conference 1995: 223-232
  98. Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174
  99. Maurice A. W. Houtsma, Arun N. Swami: Set-Oriented Mining for Association Rules in Relational Databases. ICDE 1995: 25-33
  100. Rakesh Agrawal, Ramakrishnan Srikant: Mining Sequential Patterns. ICDE 1995: 3-14
  101. Show-Jane Yen, Arbee L. P. Chen: An Efficient Algorithm for Deriving Compact Rules from Databases. DASFAA 1995: 364-371
  102. Jong Soo Park, Ming-Syan Chen, Philip S. Yu: Efficient Parallel and Data Mining for Association Rules. CIKM 1995: 31-36
  103. Jiawei Han: Mining Knowledge at Multiple Concept Levels. CIKM 1995: 19-24
  104. Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155
  105. Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994: 487-499
  106. Jason Tsong-Li Wang, Gung-Wei Chirn, Thomas G. Marr, Bruce A. Shapiro, Dennis Shasha, Kaizhong Zhang: Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results. SIGMOD Conference 1994: 115-125
  107. Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429
  108. Rakesh Agrawal, Michael J. Carey, Christos Faloutsos, Sakti P. Ghosh, Maurice A. W. Houtsma, Tomasz Imielinski, Balakrishna R. Iyer, A. Mahboob, H. Miranda, Ramakrishnan Srikant, Arun N. Swami: Quest: A Project on Database Mining. SIGMOD Conference 1994: 514
  109. Rakesh Agrawal: Tutorial Database Mining. PODS 1994: 75-76
  110. Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: Extending a DBMS to Support 3D Medical Images. ICDE 1994: 314-325
  111. Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: A Prototype 3-D Medical Image Database System. IEEE Data Eng. Bull. 16(1): 38-42(1993)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:14 2009