Sublinear Algorithms for Big Data Applications

This book explores sublinear algorithms and their application to big data problems. Sublinear algorithms solve problems using less than linear time or space relative to input size, with provable theoretical bounds. The authors bridge the gap between theoretical computer science and practical big data applications.

The book first presents the foundations of sublinear algorithms, including key ingredients and common techniques for deriving sublinear algorithm bounds. It then demonstrates how to apply these algorithms to three big data application domains: wireless sensor networks, big data processing in MapReduce, and smart grids.

For each domain, the authors show how problems are formalized, solved, and evaluated, linking theoretical research results with real-world problems. The book is intended for researchers and practitioners interested in efficient big data processing.

The book is part of the SpringerBriefs in Computer Science series and is supported by various NSF and RGC grants.