Data Streams by Charu C. Aggarwal (Editor)

List of Figures     xi
List of Tables     xv
Preface     xvii
An Introduction to Data Streams   Charu C. Aggarwal     1
Introduction     1
Stream Mining Algorithms     2
Conclusions and Summary     6
References     7
On Clustering Massive Data Streams: A Summarization Paradigm   Charu C. Aggarwal   Jiawei Han   Jianyong Wang   Philip S. Yu     9
Introduction     10
The Micro-clustering Based Stream Mining Framework     12
Clustering Evolving Data Streams: A Micro-clustering Approach     17
Micro-clustering Challenges     18
Online Micro-cluster Maintenance: The CluStream Algorithm     19
High Dimensional Projected Stream Clustering     22
Classification of Data Streams: A Micro-clustering Approach     23
On-Demand Stream Classification     24
Other Applications of Micro-clustering and Research Directions     26
Performance Study and Experimental Results     27
Discussion     36
References     36
A Survey of Classification Methods in Data Streams   Mohamed Medhat Gaber   Arkady Zaslavsky   Shonali Krishnaswamy     39
Introduction     39
Research Issues     41
Solution Approaches     43
Classification Techniques     44
Ensemble Based Classification     45
Very Fast Decision Trees (VFDT)     46
On Demand Classification     48
Online Information Network (OLIN)     48
LWClass Algorithm     49
ANNCAD Algorithm     51
SCALLOP Algorithm     51
Summary     52
References     53
Frequent Pattern Mining in Data Streams   Ruoming Jin   Gagan Agrawal     61
Introduction     61
Overview     62
New Algorithm     67
Work on Other Related Problems     79
Conclusions and Future Directions     80
References     81
A Survey of Change Diagnosis Algorithms in Evolving Data Streams   Charu C. Aggarwal     85
Introduction     86
The Velocity Density Method     88
Spatial Velocity Profiles     93
Evolution Computations in High Dimensional Case     95
On the use of clustering for characterizing stream evolution     96
On the Effect of Evolution in Data Mining Algorithms     97
Conclusions     100
References     101
Multi-Dimensional Analysis of Data Streams Using Stream Cubes   Jiawei Han   Y. Dora Cai   Yixin Chen   Guozhu Dong   Jian Pei   Benjamin W. Wah   Jianyong Wang     103
Introduction     104
Problem Definition     106
Architecture for On-line Analysis of Data Streams     108
Tilted time frame     108
Critical layers     110
Partial materialization of stream cube     111
Stream Data Cube Computation     112
Algorithms for cube computation     115
Performance Study     117
Related Work     120
Possible Extensions     121
Conclusions     122
References     123
Load Shedding in Data Stream Systems   Brian Babcock   Mayur Datar   Rajeev Motwani     127
Load Shedding for Aggregation Queries     128
Problem Formulation     129
Load Shedding Algorithm     133
Extensions     141
Load Shedding in Aurora     142
Load Shedding for Sliding Window Joins     144
Load Shedding for Classification Queries     145
Summary     146
References     146
The Sliding-Window Computation Model and Results   Mayur Datar   Rajeev Motwani     149
Motivation and Road Map     150
A Solution to the BasicCounting Problem     152
The Approximation Scheme     154
Space Lower Bound for BasicCounting Problem     157
Beyond 0's and 1's     158
References and Related Work     163
Conclusion     164
References     166
A Survey of Synopsis Construction in Data Streams   Charu C. Aggarwal   Philip S. Yu     169
Introduction     169
Sampling Methods     172
Random Sampling with a Reservoir     174
Concise Sampling     176
Wavelets     177
Recent Research on Wavelet Decomposition in Data Streams     182
Sketches     184
Fixed Window Sketches for Massive Time Series     185
Variable Window Sketches of Massive Time Series     185
Sketches and their applications in Data Streams     186
Sketches with p-stable distributions      190
The Count-Min Sketch     191
Related Counting Methods: Hash Functions for Determining Distinct Elements     193
Advantages and Limitations of Sketch Based Methods     194
Histograms     196
One Pass Construction of Equi-depth Histograms     198
Constructing V-Optimal Histograms     198
Wavelet Based Histograms for Query Answering     199
Sketch Based Methods for Multi-dimensional Histograms     200
Discussion and Challenges     200
References     202
A Survey of Join Processing in Data Streams   Junyi Xie   Jun Yang     209
Introduction     209
Model and Semantics     210
State Management for Stream Joins     213
Exploiting Constraints     214
Exploiting Statistical Properties     216
Fundamental Algorithms for Stream Join Processing     225
Optimizing Stream Joins     227
Conclusion     230
Acknowledgments     232
References     232
Indexing and Querying Data Streams   Ahmet Bulut   Ambuj K. Singh     237
Introduction     238
Indexing Streams     239
Preliminaries and definitions     239
Feature extraction     240
Index maintenance     244
Discrete Wavelet Transform     246
Querying Streams     248
Monitoring an aggregate query     248
Monitoring a pattern query     251
Monitoring a correlation query     252
Related Work     254
Future Directions     255
Distributed monitoring systems     255
Probabilistic modeling of sensor networks     256
Content distribution networks     256
Chapter Summary     257
References     257
Dimensionality Reduction and Forecasting on Streams   Spiros Papadimitriou   Jimeng Sun   Christos Faloutsos     261
Related work     264
Principal component analysis (PCA)     265
Auto-regressive models and recursive least squares     267
Muscles     269
Tracking correlations and hidden variables: Spirit     271
Putting Spirit to work     276
Experimental case studies     278
Performance and accuracy     283
Conclusion     286
Acknowledgments     286
References      287
A Survey of Distributed Mining of Data Streams   Srinivasan Parthasarathy   Amol Ghoting   Matthew Eric Otey     289
Introduction     289
Outlier and Anomaly Detection     291
Clustering     295
Frequent itemset mining     296
Classification     297
Summarization     298
Mining Distributed Data Streams in Resource Constrained Environments     299
Systems Support     300
References     304
Algorithms for Distributed Data Stream Mining   Kanishka Bhaduri   Kamalika Das   Krishnamoorthy Sivakumar   Hillol Kargupta   Ran Wolff   Rong Chen     309
Introduction     310
Motivation: Why Distributed Data Stream Mining?     311
Existing Distributed Data Stream Mining Algorithms     312
A local algorithm for distributed data stream mining     315
Local Algorithms: definition     315
Algorithm details     316
Experimental results     318
Modifications and extensions     320
Bayesian Network Learning from Distributed Data Streams     321
Distributed Bayesian Network Learning Algorithm      322
Selection of samples for transmission to global site     323
Online Distributed Bayesian Network Learning     324
Experimental Results     326
Conclusion     326
References     329
A Survey of Stream Processing Problems and Techniques in Sensor Networks   Sharmila Subramaniam   Dimitrios Gunopulos     333
Challenges     334
The Data Collection Model     335
Data Communication     335
Query Processing     337
Aggregate Queries     338
Join Queries     340
Top-k Monitoring     341
Continuous Queries     341
Compression and Modeling     342
Data Distribution Modeling     343
Outlier Detection     344
Application: Tracking of Objects using Sensor Networks     345
Summary     347
References     348
Index     353