|
|
|
|
Data Streams: Algorithms and Applications
Foundations and Trends® in
Theoretical Computer Science
Volume 1 Issue 2
DOI: 10.1561/0400000002
Data Streams: Algorithms and Applications
S. Muthukrishnan
Rutgers University, New Brunswick, NJ, USA,
muthu@cs.rutgers.edu
Abstract
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. Researchers in Theoretical Computer Science, Databases, IP Networking
and Computer Systems are working on the data stream challenges. This article is an overview and survey of data stream algorithmics
and is an updated version of [1].
|
|
|
|
|
|
|
|
|