Wang, Dan.

Sublinear Algorithms for Big Data Applications. - Cham : Springer International Publishing, 2015. - 1 online resource (94 p.) - eBooks on Demand SpringerBriefs in Computer Science . - SpringerBriefs in Computer Science .

Preface; Contents; 1 Introduction ; 1.1 Big Data: The New Frontier; 1.2 Sublinear Algorithms; 1.3 Book Organization; References; 2 Basics for Sublinear Algorithms; 2.1 Introduction; 2.2 Foundations; 2.2.1 Approximation and Randomization; 2.2.2 Inequalities and Bounds; 2.2.3 Classification of Sublinear Algorithms; 2.3 Examples; 2.3.1 Estimating the User Percentage: The Very First Example; 2.3.2 Finding Distinct Elements; 2.3.2.1 The Initial Algorithm; 2.3.2.2 Median Trick in Boosting Confidence; 2.3.3 Two-Cat Problem; 2.4 Summary and Discussions; References 3 Application on Wireless Sensor Networks 3.1 Introduction; 3.1.1 Background and Related Work; 3.1.2 Chapter Outline; 3.2 System Architecture; 3.2.1 Preliminaries; 3.2.2 Network Construction; 3.2.3 Specifying the Structure of the Layers; 3.2.4 Data Collection and Aggregation; 3.3 Evaluation of the Accuracy and the Number of Sensors Queried; 3.3.1 MAX and MIN Queries; 3.3.2 QUANTILE Queries; 3.3.3 AVERAGE and SUM Queries; 3.3.3.1 The Initial Algorithm; 3.3.3.2 Utilizing Statistical Information About the Behavior of Data; 3.3.4 Effect of the Promotion Probability p; 3.4 Energy Consumption 3.4.1 Overall Lifetime of the System3.5 Evaluation Results; 3.5.1 System Settings; 3.5.2 Layers vs. Accuracy; 3.5.2.1 QUANTILE Queries; 3.5.2.2 AVERAGE Queries; 3.6 Practical Variations of the Architecture; 3.7 Summary and Discussions; References; 4 Application on Big Data Processing ; 4.1 Introduction; 4.1.1 Big Data Processing; 4.1.2 Overview of MapReduce; 4.1.3 The Data Skew Problem; 4.1.4 Chapter Outline; 4.2 Server Load Balancing: Analysis and Problem Formulation; 4.2.1 Background and Motivation; 4.2.2 Problem Formulation; 4.2.3 Input Models; 4.3 A 2-Competitive Fully Online Algorithm 4.4 A Sampling-Based Semi-online Algorithm4.4.1 Sample Size; 4.4.2 Heavy Keys; 4.4.3 A Sample-Based Algorithm; 4.5 Performance Evaluation; 4.5.1 Simulation Setup; 4.5.2 Results on Synthetic Data; 4.5.3 Results on Real Data; 4.6 Summary and Discussions; References; 5 Application on a Smart Grid ; 5.1 Introduction; 5.1.1 Background and Related Work; 5.1.2 Chapter Outline; 5.2 Smart Meter Data Analysis; 5.2.1 Incomplete Data Problem; 5.2.2 User Usage Behavior; 5.3 Load Profile Classification; 5.3.1 Sublinear Algorithm on Testing Two Distributions; 5.3.2 Sublinear Algorithm for Classifying Users 5.4 Differentiated Services5.5 Performance Evaluation; 5.6 Summary and Discussions; References; 6 Concluding Remarks ; 6.1 Summary of the Book; 6.2 Opportunities and Challenges

9783319204482 54.99 (NL),54.99 (1U)


Big data.
Computer algorithms.


Electronic books.

QA75.5-76.95

004