Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science,) [Paperback]

S. Muthukrishnan (Author)

Book Description

Series: Foundations and Trends in Theoretical Computer Science, | Publication Date: January 10, 2005

Data stream algorithms as an active research agenda emerged only over the past few years, even though the concept of making few passes over the data for performing computations has been around since the early days of Automata Theory. The data stream agenda now pervades many branches of Computer Science including databases, networking, knowledge discovery and data mining, and hardware systems. Industry is in synch too, with Data Stream Management Systems (DSMSs) and special hardware to deal with data speeds. Even beyond Computer Science, data stream concerns are emerging in physics, atmospheric science and statistics. Data Streams: Algorithms and Applications focuses on the algorithmic foundations of data streaming. 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.

Product Details

• Paperback: 136 pages
• Publisher: Now Publishers Inc (January 10, 2005)
• Language: English
• ISBN-10: 193301914X
• ISBN-13: 978-1933019147
• Product Dimensions: 9.1 x 6.1 x 0.4 inches
• Shipping Weight: 7.8 ounces (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #2,261,671 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

3 of 3 people found the following review helpful:

4.0 out of 5 stars An accessible, but too short, survey of an important area, September 27, 2010

By 

Evgeny Kirpichov - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science,) (Paperback)

The book lists a fair number of important problems in the rapidly developing area of data stream algorithms (algorithms for processing huge amounts of data in one or more passes without ever loading the entire dataset into memory, for example network traffic or webpage hits). Every problem is explained and then the author discusses the known ideas for solving this problem and gives references to papers where the solutions are presented in full. The book is very accessible, does not have a lot of math and has only the simplest outlines of algorithms and proofs (for others, the reader is sent to the original sources). This is both good and bad: it is more like a survey than like a textbook; I expected to learn more from the book itself. Anyways, as a survey the book is invaluable and I'm grateful to the author for producing it. Also, though I didn't learn many algorithms and proofs, I learn quite a few good ideas; the book is well-structured and ideas are presented explicitly.