Mining data streams under block evolution

ABSTRACT

In this paper we survey recent work on incremental data mining model maintenance and change detection under block evolution. In block evolution, a dataset is updated periodically through insertions and deletions of blocks of records at a time. We describe two techniques: (1) We describe a generic algorithm for model maintenance that takes any traditional incremental data mining model maintenance algorithm and transforms it into an algorithm that allows restrictions on a temporal subset of the database. (2) We also describe a generic framework for change detection, that quantifies the difference between two datasets in terms of the data mining models they induce.

REFERENCES

• 1: Proceedings of the 26th International Conference on Very Large Data Bases, September 2000
• 2: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Aqua: A Fast Decision Support Systems Using Approximate Query Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.754-757, September 07-10, 1999
• 3: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, The Aqua approximate query answering system, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.574-576, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.275-286, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Rakesh Agrawal , Hiekki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 6: R. Agrawal and G. Psaila. Acive data mining. Proceedings of the first international conference on knowledge discovery and data mining, 1995.
• 7: R. Agrawal and A. Swami. A one-pass space-efficient algorithm for finding quantiles. In S. Chaudhuri, A. Deshpande, and R. Krishnamurthy, editors, Proceedings of the 7th International Conference on Management of Data (COMAD), December 1995.
• 8: Damianos Chatziantoniou , Michael O. Akinde , Theodore Johnson , Samuel Kim, The MD-join: An Operator for Complex OLAP, Proceedings of the 17th International Conference on Data Engineering, p.524-533, April 02-06, 2001
• 9: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 10: Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303978]
• 11: Khaled Alsabti , Sanjay Ranka , Vineet Singh, A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data, Proceedings of the 23rd International Conference on Very Large Data Bases, p.346-355, August 25-29, 1997
• 12: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 13: T. W. Anderson. The statistical analysis of time series. John Wiley & Sons, Inc., 1971.
• 14: Proceedings of the 25th International Conference on Very Large Data Bases, September 1999
• 15: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 16: D. Barbará, W. DuMouchel, C. Faloutsos, P. J. Haas, J. M. Hellerstein, Y. E. Ioannidis, H. V. Jagadish, T. Johnson, R. T. Ng, V. Poosala, K. A. Ross, and K. C. Sevcik. The new jersey data reduction report. Data Engineering Bulletin, 20(4):3-45, 1997.
• 17: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, 1984.
• 18: Soumen Chakrabarti , Sunita Sarawagi , Byron Dom, Mining Surprising Patterns Using Temporal Description Length, Proceedings of the 24rd International Conference on Very Large Data Bases, p.606-617, August 24-27, 1998
• 19: Ad Hoc OLAP: Expression and Evaluation, Proceedings of the 15th International Conference on Data Engineering, p.250, March 23-26, 1999
• 20: Damianos Chatziantoniou , Kenneth A. Ross, Querying Multiple Features of Groups in Relational Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.295-306, September 03-06, 1996
• 21: Surajit Chaudhuri , Umeshwar Dayal , Venkatesh Ganti, Database Technology for Decision Support Systems, Computer, v.34 n.12, p.48-55, December 2001 [doi>10.1109/2.970575]
• 22: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 23: Zhiyuan Chen , Johannes Gehrke , Flip Korn, Query optimization in compressed database systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.271-282, May 21-24, 2001, Santa Barbara, California, United States
• 24: 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
• 25: 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
• 26: D. Cheung, T. Vincent, and W. Benjamin. Maintenance of discovered knowledge: A case in multi-level association rules. In Proceedings of the second international conference on knowledge discovery in databases, August 1996.
• 27: Corinna Cortes , Kathleen Fisher , Daryl Pregibon , Anne Rogers, Hancock: a language for extracting signatures from data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.9-17, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347094]
• 28: Ralph B D'Agostino , Michael A Stephens, Goodness-of-fit techniques, Marcel Dekker, Inc., New York, NY, 1986
• 29: A. Delis, C. Faloutsos, and S. Ghandeharizadeh, editors. SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania, USA. ACM Press, 1999.
• 30: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 31: 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
• 32: M. Ester, H.-P. Kriegel, and X. Xu. A database interface for clustering in large spatial databases. In Proc. of the 1st Int'l Conference on Knowledge Discovery in Databases and Data Mining, Montreal, Canada, August 1995.
• 33: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 34: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, Testing and spot-checking of data streams (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.165-174, January 09-11, 2000, San Francisco, California, United States
• 35: Jessica H. Fong , Martin Strauss, An Approximate Lp-Difference Algorithm for Massive Data Streams, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.193-204, February 01, 2000
• 36: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, DEMON: Mining and Monitoring Evolving Data, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.50-63, January 2001 [doi>10.1109/69.908980]
• 37: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 38: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 39: Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
• 40: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 41: Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
• 42: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 43: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 44: Proceedings of the 1998 ACM SIGMOD international conference on Management of data, June 1998
• 45: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 46: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 47: M. R. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. Technical Report 1998-011, Digital Eqipment Corporation, Systems Research Center, May, 1998.
• 48: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 49: Fredrik Kilander , Carl Gustaf Jansson, COBBIT - A Control Procedure for COBWEB in the Presence of Concept Drift, Proceedings of the European Conference on Machine Learning, p.244-261, April 05-07, 1993
• 50: M. Klenner and U. Hahn. Concept versioning: A methodology for tracking evolutionary concept drift in dynamic concept systems. In A. G. Cohn, editor, Proceedings of the Eleventh European Conference on Artificial Intelligence, pages 473-477, Chichester, Aug. 8-12 1994. John Wiley and Sons.
• 51: Ling Liu , Calton Pu , Wei Tang , David Buttler , John Biggs , Tong Zhou , Paul Benninghoff , Wei Han , Fenghua Yu, CQ: a personalized update monitoring toolkit, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.547-549, June 01-04, 1998, Seattle, Washington, United States
• 52: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
• 53: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.251-262, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 54: L. O'Callaghan, N. Mishra, A. Meyerson, S. Guha, and R. Motwani. High-performance clustering of streams and large data sets. In Proceedings of the 18th International Conference on Data Engineering, 2002.
• 55: Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
• 56: Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online Dynamic Reordering for Interactive Data Processing, Proceedings of the 25th International Conference on Very Large Data Bases, p.709-720, September 07-10, 1999
• 57: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 58: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• 59: P. Utgoff. ID5: An incremental ID3. In Proceedings of the Fifth International Conference on Machine Learning, pages 107-120. Morgan Kaufmann, 1988.
• 60: Gerhard Widmer , Miroslav Kubat, Learning in the presence of concept drift and hidden contexts, Machine Learning, v.23 n.1, p.69-101, April 1996 [doi>10.1023/A:1018046501280]
• 61: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 62: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: A New Data Clustering Algorithm and Its Applications, Data Mining and Knowledge Discovery, v.1 n.2, p.141-182, 1997 [doi>10.1023/A:1009783824328]