Mining inter-transaction associations with templates

ABSTRACT

Multi-dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. “After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away” is an example of such rules. Since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. In order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction associations to be mined. With the guidance of templates, several optimization techniques are devised to speed up the discovery of inter-transaction association rules. We show, through a series of experiments, that these optimization techniques can yield significant performance benefits.

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
• AS96: R. Agrawal and J.C. Sharer. Parallel mining of association rules: Design, implementation and experience. Technical Report IBM Research Report RJ 10004, 1996.
• BP9?: Elena Baralis , Giuseppe Psaila, Designing Templates for Mining Association Rules, Journal of Intelligent Information Systems, v.9 n.1, p.7-32, July/Aug. 1997 [doi>10.1023/A:1008637019359]
• BWJ96: Claudio Bettini , X. Sean Wang , Sushil Jajodia, Testing complex temporal relationships involving multiple granularities and its application to data mining (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.68-78, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237680]
• BWJ98: C. Bettini, X. Wang, and S. Jajodia. Mining temporal relationships with multiple granularities in time sequences. Da~a Engineering, 21(1):32-38, March 1998.
• DLM+98: G. Das, K.-I. Lin, H. Mannila, G. Renganathan, and P. Smyth. R. ule discovery from time series. In Proc. of the second ~nternationai Conference on Knowledge Discovery and Data Mining, pages 16-22, New York, USA, August 1998.
• HF95: J. Han and Y. Fu. Meta-rule-guided mining of association rules in relational databases. In Proc. I st Intl. Workshop on Integration of Knowledge Discovery with Deductive and Object-Oriented Databases, pages 39-46, Singapore, December 1995.
• LHF98: H. Lu, J. Han, and L. Feng. Stock movement prediction and n-dimensional inter-transaction association rules. In Proe. A CM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Dis. covery, pages 12:1-12:7, Seattle, Washington, June 1998.
• MPC96: Rosa Meo , Giuseppe Psaila , Stefano Ceri, A New SQL-like Operator for Mining Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.122-133, September 03-06, 1996
• MT96: H. Mannila and H. Toivonen. Discovering generalized episodes using minimal occurrences. In Proc. $nd Intl. Conf. Knowledge Discovery and Data Mining, pages 146-151, Portland, Oregon, August 1996.
• MTV97: H. Mannila, H. Toivonen, and A. Verkamo. Discovering frequent episodes in event sequences. Technical Report Department of Computer Science, Report C- 1997-15, February 1997.
• NLHP98: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• SVA97: R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. In Proc. 3rd Intl. Conf. Knowledge Discovery and Data Mining, pages 67-73, Newport Beach, California, August 1997.
• TUA+98: Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.1-12, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases; Transaction processing

General Terms:
Design, Documentation, Experimentation, Management, Measurement, Performance, Theory