Designing an inductive data stream management system: the stream mill experience

ABSTRACT

There has been much recent interest in on-line data mining. Existing mining algorithms designed for stored data are either not applicable or not effective on data streams, where real-time response is often needed and data characteristics change frequently. Therefore, researchers have been focusing on designing new and improved algorithms for on-line mining tasks, such as classification, clustering, frequent itemsets mining, pattern matching, etc. Relatively little attention has been paid to designing DSMSs, which facilitate and integrate the task of mining data streams---i.e., stream systems that provide Inductive functionalities analogous to those provided by Weka and MS OLE DB for stored data. In this paper, we propose the notion of an Inductive DSMS---a system that besides providing a rich library of inter-operable functions to support the whole mining process, also supports the essentials of DSMS, including optimization of continuous queries, load shedding, synoptic constructs, and non-stop computing. Ease-of-use and extensibility are additional desiderata for the proposed Inductive DSMS. We first review the many challenges involved in realizing such a system and then present our approach of extending the Stream Mill DSMS toward that goal. Our system features (i) a powerful query language where mining methods are expressed via aggregates for generic streams and arbitrary windows, (ii) a library of fast and light mining algorithms, and (iii) an architecture that makes it easy to customize and extend existing mining methods and introduce new ones.

REFERENCES

• 1: Atlas user manual. http://wis.cs.ucla.edu/atlas.
• 2: DB2 Universal Database http://publib.boulder.ibm.com/infocenter/db2luw/v8/index.jsp.
• 3: Decision Tree Entropy Calculation http://decisiontrees.net/? q=node/27.
• 4: IBM. DB2 Intelligent Miner http://www-306.ibm.com/software/data/iminer.
• 5: ORACLE. Oracle Data Miner Release 10gr2 http://www.oracle.com/technology/products/bi/odm.
• 6: A. Arasu, S. Babu, and J. Widom. Cql: A language for continuous queries over streams and relations. In DBPL, pages 1--19, 2003.
• 7: Arvind Arasu , Jennifer Widom, Resource sharing in continuous sliding-window aggregates, Proceedings of the Thirtieth international conference on Very large data bases, p.336-347, August 31-September 03, 2004, Toronto, Canada
• 8: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 9: Yijian Bai , Hetal Thakkar , Haixun Wang , Chang Luo , Carlo Zaniolo, A data stream language and system designed for power and extensibility, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183664]
• 10: Toon Calders, Bart Goethals, and Adriana Prado. Integrating pattern mining in relational databases. In PKDD, volume 4213 of Lecture Notes in Computer Science, pages 454--461. Springer, 2006.
• 11: W. Cheung and O. R. Zaiane. Incremental mining of frequent patterns without candidate generation or support. In DEAS, 2003.
• 12: 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, p.59-66, November 01-04, 2004
• 13: F. Chu and C. Zaniolo. Fast and light boosting for adaptive mining of data streams. In PAKDD, volume 3056, 2004.
• 14: Weka 3: data mining with open source machine learning software in java. http://www.cs.waikato.ac.nz.
• 15: Guozhu Dong, Jiawei Han, Laks V. S. Lakshmanan, Jian Pei, Haixun Wang, and Philip S. Yu. Online mining of changes from data streams: Research problems and preliminary results. In SIGMOD, 2003.
• 16: Martin Ester , Hans-Peter Kriegel , Jörg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998
• 17: Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Second International Conference on Knowledge Discovery and Data Mining, pages 226--231, 1996.
• 18: 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]
• 19: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 20: Sirish Chandrasekaran , Owen Cooper , Amol Deshpande , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong , Sailesh Krishnamurthy , Samuel R. Madden , Fred Reiss , Mehul A. Shah, TelegraphCQ: continuous dataflow processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872857]
• 21: Stream Mill Examples. Approximate Frequent Items http://wis.cs.ucla.edu/stream-mill/examples/freq.html.
• 22: E. Forgy. Cluster analysis of multivariate data: efficiency versus interpretability of classifications. Biometrics, page 768, 1965.
• 23: George Forman, Tackling concept drift by temporal inductive transfer, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148216]
• 24: J. Han, Y. Fu, W. Wang, K. Koperski, and O. R. Zaiane. DMQL: A data mining query language for relational databases. In Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD), pages 27--33, Montreal, Canada, June 1996.
• 25: 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
• 26: Tomasz Imieliński , Aashu Virmani, MSQL: A Query Language for Database Mining, Data Mining and Knowledge Discovery, v.3 n.4, p.373-408, December 1999 [doi>10.1023/A:1009816913055]
• 27: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 28: Nan Jiang , Le Gruenwald, Research issues in data stream association rule mining, ACM SIGMOD Record, v.35 n.1, p.14-19, March 2006 [doi>10.1145/1121995.1121998]
• 29: Minsoo Kim, Jae-Hyun Seo, II-Ahn Cheong, and Bong-Nam Noh. Fuzzy Systems and Knowledge Discovery, chapter Auto-generation of Detection Rules with Tree Induction Algorithm, pages 160--169. Springer Berlin / Heidelberg, 2005.
• 30: Yan-Nei Law , Haixun Wang , Carlo Zaniolo, Query languages and data models for database sequences and data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.492-503, August 31-September 03, 2004, Toronto, Canada
• 31: Carson Kai-Sang Leung , Quamrul I. Khan , Tariqul Hoque, CanTree: A Tree Structure for Efficient Incremental Mining of Frequent Patterns, Proceedings of the Fifth IEEE International Conference on Data Mining, p.274-281, November 27-30, 2005 [doi>10.1109/ICDM.2005.38]
• 32: Chang Luo , Hetal Thakkar , Haixun Wang , Carlo Zaniolo, A native extension of SQL for mining data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066271]
• 33: 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
• 34: Barzan Mozafari, Hetal Thakkar, and Carlo Zaniolo. Verifying and mining frequent patterns from large windows over data streams. In International Conference on Data Engineering (ICDE), 2008.
• 35: Chang-Shing Perng , Douglas Stott Parker, Jr., SQL/LPP: A Time Series Extension of SQL Based on Limited Patience Patterns, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.218-227, August 30-September 03, 1999
• 36: R. Ramakrishnan, D. Donjerkovic, A. Ranganathan, K. Beyer, and M. Krishnaprasad. Srql: Sorted relational query language, 1998.
• 37: Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Optimization of sequence queries in database systems, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.71-81, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375563]
• 38: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 39: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, Sequence query processing, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.430-441, May 24-27, 1994, Minneapolis, Minnesota, United States
• 40: A. Siebes. Where is the mining in kdid? (invited talk). In Fourth Int. Workshop on Knowledge Discovery in Inductive Databases,, 2005.
• 41: Mark Sullivan, Tribeca: A Stream Database Manager for Network Traffic Analysis, Proceedings of the 22th International Conference on Very Large Data Bases, p.594, September 03-06, 1996
• 42: Zhaohui Tang , Jamie Maclennan , Peter Pyungchul Kim, Building data mining solutions with OLE DB for DM and XML for analysis, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083805]
• 43: 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]
• 44: Carlo Zaniolo. Mining databases and data streamswith query languages and rules (invited talk). In Fourth Int. Workshop on Knowledge Discovery in Inductive Databases,, 2005.
• 45: Fred Zemke, Andrew Witkowski, Mitch Cherniak, and Latha Colby. Pattern matching in sequences of rows. Technical report, Oracle and IBM, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

General Terms:
Design, Languages, Management

Keywords:
data stream mining language, data stream mining system, integration of online mining in a DSMS