Algorithms and Data Structures for Massive Datasets (MEAP v3)

The unprecedented growth of data in recent years is putting the spotlight on the data structures and algorithms that can efficiently handle large datasets. In this book, we present you with a basic suite of data structures and algorithms designed to index, query, and analyze massive data. What prompted us to write this book is that many of the novel data structures and algorithms that run underneath Google, Facebook, Dropbox and many others, are making their way into the mainstream algorithms curricula very slowly. Often the main resources on this subject are research papers filled with sophisticated and enlightening theory, but with little instruction on how to configure the data structures in a practical setting, or when to use them. Our goal was to present these exciting and cutting-edge topics in one place, in a practical and friendly tone. Mathematical intuition is important for understanding the subject, and we try to cultivate it without including a single proof. Plentiful illustrations are used to illuminate some of the more challenging material. Large datasets arise in a variety of disciplines, from bioinformatics and finance, to sensor data and social networks, and our use cases are designed to reflect that. Massive modern datasets make traditional data structures and algorithms grind to a halt. This fun and practical guide introduces cutting-edge techniques that can reliably handle even the largest distributed datasets.In Algorithms and Data Structures for Massive Datasets you will learn: Probabilistic sketching data structures for practical problems Choosing the right database engine for your application Evaluating and designing efficient on-disk data structures and algorithms Understanding the algorithmic trade-offs involved in massive-scale systems Deriving basic statistics from streaming data Correctly sampling streaming data Computing percentiles with limited space resources Algorithms and Data Structures for Massive Datasets reveals a toolbox of new methods that are perfect for handling modern big data applications. You'll explore the novel data structures and algorithms that underpin Google, Facebook, and other enterprise applications that work with truly massive amounts of data. These effective techniques can be applied to any discipline, from finance to text analysis. Graphics, illustrations, and hands-on industry examples make complex ideas practical to implement in your projects—and there's no mathematical proofs to puzzle over. Work through this one-of-a-kind guide, and you'll find the sweet spot of saving space without sacrificing your data's accuracy. About the technology Standard algorithms and data structures may become slow—or fail altogether—when applied to large distributed datasets. Choosing algorithms designed for big data saves time, increases accuracy, and reduces processing cost. This unique book distills cutting-edge research papers into practical techniques for sketching, streaming, and organizing massive datasets on-disk and in the cloud. About the book Algorithms and Data Structures for Massive Datasets introduces processing and analytics techniques for large distributed data. Packed with industry stories and entertaining illustrations, this friendly guide makes even complex concepts easy to understand. You'll explore real-world examples as you learn to map powerful algorithms like Bloom filters, Count-min sketch, HyperLogLog, and LSM-trees to your own use cases. What's inside Probabilistic sketching data structures Choosing the right database engine Designing efficient on-disk data structures and algorithms Algorithmic tradeoffs in massive-scale systems Computing percentiles with limited space resources About the reader Examples in Python, R, and pseudocode. About the author Dzejla Medjedovic earned her PhD in the Applied Algorithms Lab at Stony Brook University, New York. Emin Tahirovic earned his PhD in biostatistics from University of Pennsylvania. Illustrator Ines Dedovic earned her PhD at the Institute for Imaging and Computer Vision at RWTH Aachen University, Germany. Table of Contents 1 Introduction PART 1 HASH-BASED SKETCHES 2 Review of hash tables and modern hashing 3 Approximate membership: Bloom and quotient filters 4 Frequency estimation and count-min sketch 5 Cardinality estimation and HyperLogLog PART 2 REAL-TIME ANALYTICS 6 Streaming data: Bringing everything together 7 Sampling from data streams 8 Approximate quantiles on data streams PART 3 DATA STRUCTURES FOR DATABASES AND EXTERNAL MEMORY ALGORITHMS 9 Introducing the external memory model 10 Data structures for databases: B-trees, Bε-trees, and LSM-trees 11 External memory sorting Massive modern datasets make traditional data structures and algorithms grind to a halt. This fun and practical guide introduces cutting-edge techniques that can reliably handle even the largest distributed datasets. In Algorithms and Data Structures for Massive Datasets you will learn: Probabilistic sketching data structures for practical problems Choosing the right database engine for your application Evaluating and designing efficient on-disk data structures and algorithms Understanding the algorithmic trade-offs involved in massive-scale systems Deriving basic statistics from streaming data Correctly sampling streaming data Computing percentiles with limited space resources Algorithms and Data Structures for Massive Datasets reveals a toolbox of new methods that are perfect for handling modern big data applications. You'll explore the novel data structures and algorithms that underpin Google, Facebook, and other enterprise applications that work with truly massive amounts of data. These effective techniques can be applied to any discipline, from finance to text analysis. Graphics, illustrations, and hands-on industry examples make complex ideas practical to implement in your projects--and there's no mathematical proofs to puzzle over. Work through this one-of-a-kind guide, and you'll find the sweet spot of saving space without sacrificing your data's accuracy. About the Technology Standard algorithms and data structures may become slow--or fail altogether--when applied to large distributed datasets. Choosing algorithms designed for big data saves time, increases accuracy, and reduces processing cost. This unique book distills cutting-edge research papers into practical techniques for sketching, streaming, and organizing massive datasets on-disk and in the cloud. About the Book Algorithms and Data Structures for Massive Datasets introduces processing and analytics techniques for large distributed data. Packed with industry stories and entertaining illustrations, this friendly guide makes even complex concepts easy to understand. You'll explore real-world examples as you learn to map powerful algorithms like Bloom filters, Count-min sketch, HyperLogLog, and LSM-trees to your own use cases. What's Inside Probabilistic sketching data structures Choosing the right database engine Designing efficient on-disk data structures and algorithms Algorithmic tradeoffs in massive-scale systems Computing percentiles with limited space resources About the Reader Examples in Python, R, and pseudocode. About the Authors Dzejla Medjedovic earned her PhD in the Applied Algorithms Lab at Stony Brook University, New York. Emin Tahirovic earned his PhD in biostatistics from University of Pennsylvania. Illustrator Ines Dedovic earned her PhD at the Institute for Imaging and Computer Vision at RWTH Aachen University, Germany. Quotes An accessible and beautifully illustrated introduction to probabilistic and disk-based data structures and algorithms. - Marcus Young, Prosper Marketplace Upgrade your knowledge of algorithms and data structures from textbook level to real-world level. - Rui Liu, Oracle Excellently explains scalable data structures and algorithms. A must-read for any data engineer. - Alex Gout, Shopify A detailed, practical approach to dealing with distributed system and data architectures. - Satej Kumar Sahu, Honeywell Algorithms and Data Structures for Massive Datasets MEAP V03 Copyright Welcome Brief contents 1: Introduction 1.1 An example 1.1.1 An example: how to solve it 1.1.2 An example: how to solve it, take two 1.2 The structure of this book 1.3 What makes this book different and whom it is for 1.4 Why is massive data so challenging for today’s systems? 1.4.1 The CPU-memory performance gap 1.4.2 Memory hierarchy 1.4.3 What about distributed systems? 1.5 Summary 2: Review of Hash Tables and Modern Hashing 2.1 Ubiquitous hashing 2.2 A crash course on data structures 2.3 Usage scenarios in modern systems 2.3.1 Deduplication in backup/storage solutions 2.3.2 Plagiarism detection with MOSS and Rabin-Karp fingerprinting 2.4 O(1) --- what’s the big deal? 2.5 Collision Resolution: theory vs. practice 2.6 Usage scenario: How Python’s dict does it 2.7 MurmurHash 2.8 Hash Tables for Distributed Systems: Consistent Hashing 2.8.1 A typical hashing problem? 2.8.2 Hashring 2.8.3 Lookup 2.8.4 Adding a new node/resource 2.8.5 Removing a node 2.8.6 Consistent hashing scenario: Chord 2.9 Summary 3: Approximate Membership and Bloom Filter 3.1 How It Works 3.1.1 Insert 3.1.2 Lookup 3.2 Use Cases 3.2.1 Bloom Filters in Networks: Squid 3.2.2 Bitcoin mobile app 3.3 Configuring a Bloom filter for your application 3.3.1 Examples 3.4 A bit of theory 3.4.1 Can we do better? 3.5 Further reading: Bloom filter adaptations and alternatives 3.6 Quotient filter 3.6.1 Quotienting 3.6.2 Resizing 3.7 Summary 4: Frequency Estimation and Count-Min Sketch 4.1 Streaming data 4.2 Count-min sketch: how it works 4.2.1 Update 4.2.2 Estimate 4.2.3 Space and error in count-min sketch 4.3 Use cases 4.3.1 Top-k restless sleepers 4.3.2 Scaling distributional similarity of words 4.4 Range queries with count-min sketch 4.5 Approximate heavy hitters 4.5.1 Majority element 4.5.2 General heavy hitters 4.6 Summary 5: Cardinality Estimation and HyperLogLog 5.1 Counting distinct items in databases 5.2 HyperLogLog incremental design 5.2.1 The first cut --- probabilistic counting 5.2.2 Stochastic averaging or, when life gives you lemons... 5.2.3 LogLog 5.2.4 HyperLogLog --- Stochastic averaging with harmonic mean 5.3 Use case: catching worms with HLL 5.4 But how does it actually work? A mini experiment 5.4.1 The effect of the number of buckets () 5.5 Use case: Aggregation using HyperLogLog 5.6 Summary 6: Streaming Data: Bringing Everything Together 6.1 Streaming Data System – a meta-example 6.1.1 Bloom-join 6.1.2 De-duplication 6.1.3 Load balancing and tracking the network traffic 6.2 The Future is coming: in discrete batches or as a continuous stream ? 6.3 Practical constraints and concepts in data streams 6.3.1 Time 6.3.2 Small time and small space 6.3.3 Concept shifts and concept drifts 6.3.4 Sliding window model 6.4 Summary