Chapter 8

Algorithms for Data Streams

Camil Demetrescu

Camil Demetrescu

Department of Computer and Systems Science, University of Rome “La Sapienza”, Via Salaria 113, 00198 Rome, Italy

Search for more papers by this author
Irene Finocchi

Irene Finocchi

Department of Computer and Systems Science, University of Rome “La Sapienza”, Via Salaria 113, 00198 Rome, Italy

Search for more papers by this author
First published: 01 March 2007
Citations: 1

Summary

Data stream processing has recently gained increasing popularity as an effective paradigm for processing massive data sets. A wide range of applications in computational sciences generate huge and rapidly changing data streams that need to be continuously monitored in order to support exploratory analyses and to detect correlations, rare events, fraud, intrusion, and unusual or anomalous activities. Relevant examples include monitoring network traffic, online auctions, transaction logs, telephone call records, automated bank machine operations, and atmospheric and astronomical events. Due to the high sequential access rates of modern disks, streaming algorithms can also be effectively deployed for processing massive files on secondary storage, providing new insights into the solution of several computational problems in external memory. Streaming models constrain algorithms to access the input data in one or few sequential passes, using only a small amount of working memory and processing each input item quickly. Solving computational problems under these restrictions poses several algorithmic challenges.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.