Incremental and interactive sequence mining

ABSTRACT

The discovery of frequent sequences in temporal databases is an important data mining problem. Most current work assumes that the database is static, and a database update requires rediscovering all the patterns by scanning the entire old and new database. In this paper, we propose novel techniques for maintaining sequences in the presence of a) database updates, and b) user interaction (e.g. modifying mining parameters). This is a very challenging task, since such updates can invalidate existing sequences or introduce new ones. In both the above scenarios, we avoid re-executing the algorithm on the entire dataset, thereby reducing execution time. Experimental results confirm that our approach results in execution time improvements of up to several orders of magnitude in practice.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Online Generation of Association Rules, Proceedings of the Fourteenth International Conference on Data Engineering, p.402-411, February 23-27, 1998
• 2: 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
• 3: R. Feldman, Y. Aumann, A. Amir, and H. Mannila. Efficient algorithms for discovering frequent sets in incremental databases. In 2nd DMKD Workshop, 1997.
• 4: Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interesting rules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191314]
• 5: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 6: 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
• 7: T. Oates, et el. A family of algorithms for finding temporal structure in data. In 6th Workshop on AI and Statistics, 1997.
• 8: S. Parthasarathy, et el. Incremental and interactive sequence mining. TR715, CS Dept., University of Rochester, June 1999.
• 9: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 10: R. Srikant, Q. Vu, and R. Agrawal. Mining Association Rules with Item Constraints. In 3rd KDD, 1997.
• 11: S. Thomas, S. Bodgala, K. Alsabti, and S. Ranks. An efficient algorithm for incremental updation of association rules in large databases. In 3rd KDD, 1997,
• 12: Ke Wang, Discovering Patterns from Large and Dynamic Sequential Data, Journal of Intelligent Information Systems, v.9 n.1, p.33-56, July/Aug. 1997 [doi>10.1023/A:1008689103430]
• 13: Mohammed J. Zaki, Efficient enumeration of frequent sequences, Proceedings of the seventh international conference on Information and knowledge management, p.68-75, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288643]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Algorithms, Design, Experimentation, Human Factors, Management, Measurement, Performance, Theory