Research issues in data stream association rule mining

ABSTRACT

There exist emerging applications of data streams that require association rule mining, such as network traffic monitoring and web click streams analysis. Different from data in traditional static databases, data streams typically arrive continuously in high speed with huge amount and changing data distribution. This raises new issues that need to be considered when developing association rule mining techniques for stream data. This paper discusses those issues and how they are addressed in the existing literature.

REFERENCES

• 1: 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
• 2: 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
• 3: Dario Bruzzese , Paolo Buono, Combining visual techniques for Association Rules exploration, Proceedings of the working conference on Advanced visual interfaces, May 25-28, 2004, Gallipoli, Italy [doi>10.1145/989863.989930]
• 4: Y. Dora Cai , David Clutter , Greg Pape , Jiawei Han , Michael Welge , Loretta Auvil, MAIDS: mining alarming incidents from data streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007695]
• 5: Joong Hyuk Chang , Won Suk Lee, Finding recent frequent itemsets adaptively over online data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956807]
• 6: {Chang, 2004} Joong Hyuk Chang, Won Suk Lee; A Sliding Window Method for Finding Recently Frequent Itemsets over Online Data Streams; Journal of Information Science and Engineering; July 2004.
• 7: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 8: {Cheung, 1996} David W. Cheung, Jiawei Han, Vincent T. Ng, C. Y. Wong; Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique; IEEE Int'l Conf. on Data Mining; November 1996.
• 9: David Wai-Lok Cheung , Sau Dan Lee , Ben Kao, A General Incremental Technique for Maintaining Discovered Association Rules, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.185-194, April 01-04, 1997
• 10: Yun Chi , Haixun Wang , Philip S. Yu , Richard R. Muntz, Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.59-66, November 01-04, 2004
• 11: Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005 [doi>10.1145/1061318.1061325]
• 12: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Frequency Estimation of Internet Packet Streams with Limited Space, Proceedings of the 10th Annual European Symposium on Algorithms, p.348-360, September 17-21, 2002
• 13: {Gaber, 2003} Mohamed Medhat Gaber, Shonali Krishnaswamy, Arkady Zaslavsky; Adaptive Mining Techniques for Data Streams Using Algorithm Output Granularity; The Australasian Data Mining Workshop; December 2003.
• 14: {Gaber, 2004} Mohamed Medhat Gaber, Arkady Zaslavsky and Shonali Krishnaswamy; Resource-Aware Knowledge Discovery in Data Streams; Int'l Workshop on Knowledge Discovery in Data Streams; September 2004.
• 15: Mohamed Medhat Gaber , Arkady Zaslavsky , Shonali Krishnaswamy, Mining data streams: a review, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083789]
• 16: {Ghoting, 2004} Amol Ghoting, Srinivasan Parthasarathy; Facilitating Interactive Distributed Data Stream Processing and Mining; IEEE Int'l Symposium on Parallel and Distributed Processing Systems; April 2004.
• 17: {Giannella, 2003} Chris Giannella, Jiawei Han, Jian Pei, Xifeng Yan, Philip S. Yu; Mining Frequent Patterns in Data Streams at Multiple Time Granularities; Data Mining: Next Generation Challenges and Future Directions, AAAI/MIT; 2003.
• 18: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 19: {Han, 1999} Jiawei Han, Guozhu Dong, Yiwen Yin; Efficient mining of partial periodic patterns in time series database; IEEE Int'l Conf. on Data Mining; March 1999.
• 20: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 21: {Halatchev, 2005} Mihail Halatchev and Le Gruenwald; Estimating Missing Values in Related Sensor Data Streams; Int'l Conf. on Management of Data; January 2005.
• 22: Heike Hofmann , Arno P. J. M. Siebes , Adalbert F. X. Wilhelm, Visualizing association rules with interactive mosaic plots, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.227-235, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347133]
• 23: Hao Huang , Xindong Wu , Richard Relue, Association Analysis with One Scan of Databases, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.629, December 09-12, 2002
• 24: Cheqing Jin , Weining Qian , Chaofeng Sha , Jeffrey X. Yu , Aoying Zhou, Dynamically maintaining frequent items over a data stream, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956918]
• 25: {Kargupta, 2004} Hillol Kargupta, Ruchita Bhargava, Kun Liu, Michael Powers, Patrick Blair, Samuel Bushra, James Dull, Kakali Sarkar, Martin Klein, Mitesh Vasa, David Handy; VEDAS: A Mobile and Distributed Data Stream Mining System for Real-Time Vehicle Monitoring; SIAM Int'l Conf. on Data Mining; 2004.
• 26: Richard M. Karp , Scott Shenker , Christos H. Papadimitriou, A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems (TODS), v.28 n.1, p.51-55, March 2003 [doi>10.1145/762471.762473]
• 27: {Lee, 1997} S. D. Lee, David W. Cheung; Maintenance of Discovered Association Rules: When to update?; Research Issues on Data Mining and Knowledge Discovery; 1997.
• 28: {Li, 2004} Hua-Fu Li, Suh-Yin Lee, and Man-Kwan Shan; An Efficient Algorithm for Mining Frequent Itemsets over the Entire History of Data Streams; Int'l Workshop on Knowledge Discovery in Data Streams; Sept. 2004.
• 29: {Lin, 2005} Chih-Hsiang Lin, Ding-Ying Chiu, Yi-Hung Wu, Arbee L. P. Chen; Mining Frequent Itemsets from Data Streams with a Time-Sensitive Sliding Window; SIAM Int'l Conf. on Data Mining; April 2005.
• 30: {Manku, 2002} Gurmeet Singh Manku, Rajeev Motwani; Approximate Frequency Counts over Data Streams; Int'l Conf on Very Large Databases; 2002.
• 31: {Mao, 2005} Guojun Mao, Xindong Wu, Chunnian Liu, Xingquan Zhu, Gong Chen, Yue Sun, Xu Liu; Online Mining of Maximal Frequent Itemsequences from Data Streams; University of Vermont, Computer Science Technical Report CS-05-07; June 2005.
• 32: M. E. Otey , C. Wang , S. Parthasarathy , A. Veloso , W. Meira, Jr., Mining Frequent Itemsets in Distributed and Dynamic Databases, Proceedings of the Third IEEE International Conference on Data Mining, p.617, November 19-22, 2003
• 33: {Otey, 2004} Matthew Eric Otey, Srinivasan Parthasarathy, Chao Wang, Adriano Veloso, Wagner Meira Jr.; Parallel and Distributed Methods for Incremental Frequent Itemset Mining; IEEE Transactions on Systems, Man and Cybernetics; December 2004.
• 34: S. Parthasarathy , M. J. Zaki , M. Ogihara , S. Dwarkadas, Incremental and interactive sequence mining, Proceedings of the eighth international conference on Information and knowledge management, p.251-258, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320010]
• 35: Helen Pinto , Jiawei Han , Jian Pei , Ke Wang , Qiming Chen , Umeshwar Dayal, Multi-dimensional sequential pattern mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502600]
• 36: Richard Relue , Xindong Wu , Hao Huang, Efficient runtime generation of association rules, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502664]
• 37: Assaf Schuster , Ran Wolff , Dan Trock, A High-Performance Distributed Algorithm for Mining Association Rules, Proceedings of the Third IEEE International Conference on Data Mining, p.291, November 19-22, 2003
• 38: {Teng, 2004} Wei-Guang Teng, Ming-Syan Chen, and Philip S. Yu; Resource-Aware Mining with Variable Granularities in Data Streams; SIAM Int'l Conf. on Data Mining; 2004.
• 39: {Veloso, 2003} Adriano Veloso, Wagner Meira Jr., Marcio Carvalho, Srini Parthasarathy, Mohammed J. Zaki; Parallel, Incremental and Interactive Mining for Frequent Itemsets in Evolving Databases; Int'l Workshop on High Performance Data Mining: Pervasive and Data Stream Mining; May 2003.
• 40: {Veloso, 2003b} Adriano Veloso, Matthew Eric Otey, Srinivasan Parthasarathy, Wagner Meira Jr.: Parallel and Distributed Frequent Itemset Mining on Dynamic Datasets; Int'l Conf. on High Performance Computing; 2003.
• 41: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 42: {Wolff, 2004} Ran Wolff, Assaf Schuster; Association Rule Mining in Peer-to-Peer Systems; IEEE Transactions on Systems, Man and Cybernetics, Part B, Vol. 34, Issue 6; December 2004.
• 43: {Yang, 2004} Li Yang, Mustafa Sanver; Mining Short Association Rules with One Database Scan; Int'l Conf. on Information and Knowledge Engineering; June 2004.
• 44: {Yu, 2004} Jeffrey Xu Yu, Zhihong Chong, Hongjun Lu, Aoying Zhou; False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams; Int'l Conf. on Very Large Databases; 2004.
• 45: Chung-Ching Yu , Yen-Liang Chen, Mining Sequential Patterns from Multidimensional Sequence Data, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.136-140, January 2005 [doi>10.1109/TKDE.2005.13]
• 46: {Zheng, 2003} Qingguo Zheng, Ke Xu, Shilong Ma; When to Update the Sequential Patterns of Stream Data; Pacific-Asia Conf, on Knowledge Discovery and Data Mining; 2003.
• 47: {Zhu, 2002} Yunyue Zhu, Dennis Shasha; StatStream; Statistical Monitoring of Thousands of Data Streams in Real Time; Int'l Conf. on Very Large Data Bases; 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software

General Terms:
Theory