In the data stream scenario, input arrives very rapidly and there is limited memory to store the input. Algorithms have to work with one or few passes over the data, space less than linear in the input size or time significantly less than the input size. In the past few years, a new theory has emerged for reasoning about algorithms that work within these constraints on space, time and number of passes. Some of the methods rely on metric embeddings, pseudo-random computations, sparse approximation theory and communication complexity. The applications for this scenario include IP network traffic analysis, mining text message streams and processing massive data sets in general.

Data Streams: Algorithms and Applications surveys the emerging area of algorithms for processing data streams and associated applications. An extensive bibliography with over 200 entries points the reader to further resources for exploration.

Published by Now Publishers and marketed by World Scientific

Contents:

• Introduction
• Map
• The Data Stream Phenomenon
• Data Streaming: Formal Aspects
• Foundations: Basic Mathematical Ideas
• Foundations: Basic Algorithmic Techniques
• Foundations: Summary
• Streaming Systems
• New Directions
• Historic Notes
• Concluding Remarks
• Acknowledgements
• References