Tutorial proposals must clearly identify the intended audience and its assumed background. Tutorials whose audience is broader than the database research community are encouraged. Proposals must be no more than 5 pages and must provide a sense of both the scope of the tutorial and depth within the scope. The intended length of the tutorial (1.5 or 3 hours) should also be indicated, together with justification that a high-quality presentation will be achieved within the chosen time period and the indication of the main learning outcomes. Proposals should also include contact information (name, email, address, telephone number, and FAX number) and a brief bio of the presenters. If the proposed tutorial has been given previously, the proposal should include where the tutorial has been given and how it will be modified for VLDB 2006. Proposals must be submitted electronically by March 16th, 2006 (5:00 p.m. Pacific Standard Time) to: Christos Faloutsos (christos at cs cmu edu) Tutorial presentations will be published and made available to VLDB participants, and must be ready for publication by July 12th, 2006.
TITLE: Indexing and Mining Streams INSTRUCTOR: Christos Faloutsos, CMU INTENDED DURATION: 3 hours DRAFT OF FOILS (optional) A preliminary version is at www.cs.cmu.edu/~christos/TALKS/SIGMOD04-tut/faloutsos-sigmod04-v07.pdf (or, mailed separately) DESCRIPTION - OBJECTIVES How can we find patterns in a sequence of sensor measurements (eg., a sequence of temperatures, or water-pollutant measurements)? How can we compress it? What are the major tools for forecasting and outlier detection? The objective of this tutorial is to provide a concise and intuitive overview of the most important tools, that can help us find patterns in sensor sequences. Sensor data analysis becomes of increasingly high importance, thanks to the decreasing cost of hardware and the increasing on-sensor processing abilities. We review the state of the art in three related fields: (a) fast similarity search for time sequences, (b) linear forecasting with the traditional AR (autoregressive) and ARIMA methodologies and (c) non-linear forecasting, for chaotic/self-similar time sequences, using lag-plots and fractals. The emphasis of the tutorial is to give the intuition behind these powerful tools, which is usually lost in the technical literature, as well as to give case studies that illustrate their practical use. CONTENT AND OUTLINE * Similarity Search o why we need similarity search o distance functions (Euclidean, LP norms, time-warping) o fast searching (R-trees, M-trees) o feature extraction (DFT, Wavelets, SVD, FastMap) * Linear Forecasting o main idea behind linear forecasting o AR methodology o multivariate regression o Recursive Least Squares o de-trending; periodicities * Non-linear/chaotic forecasting o main idea: lag-plots o 'fractals' and 'fractal dimensions' + definition and intuition + algorithms for fast computation o case studies WHO SHOULD ATTEND Researchers that want to get up to speed with the major tools in time sequence analysis. Also, practitioners who want a concise, intuitive overview of the state of the art. RELATED PREVIOUS TUTORIALS (if any) This tutorial has also been presented in EDBT'04 and VLDB'02. The additional material is references to more recent work (time-warping indexing methods by E. Keogh, new distance functions on time series, correlation detection methods by D. Shasha) ABOUT THE INSTRUCTOR Christos Faloutsos is a Professor at Carnegie Mellon University. He has received the Presidential Young Investigator Award by the National Science Foundation (1989), three ``best paper'' awards (SIGMOD 94, VLDB 97, KDD01-runner-up), and four teaching awards. He is a member of the executive committee of SIGKDD; he has published over 100 refereed articles, one monograph, and holds four patents. His research interests include data mining, fractals, indexing methods for multimedia and text data bases, and data base performance. CONTACT INFO Christos Faloutsos Computer Science Department Carnegie Mellon University Wean Hall, room 7107 5000 Forbes Avenue Pittsburgh, PA 15213-3891 ph: 412-268.1457 FAX: 412-268.55.76 christos@cs.cmu.edu |