Algorithms and Data Structures for Massive Datasets, Video Edition

Algorithms and Data Structures for Massive Datasets, Video Edition

English | MP4 | AVC 1280×720 | AAC 44KHz 2ch | 67 Lessons (9h 53m) | 1.67 GB

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. 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.

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.

Algorithms and Data Structures for Massive Datasets introduces processing and analytics techniques for large distributed data. Packed with industry stories, 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
Table of Contents

1 Introduction
2 An example How to solve it
3 How to solve it, take two A book walkthrough
4 The structure of this book
5 Latency vs. bandwidth
6 Part 1. Hash-based sketches
7 Review of hash tables and modern hashing
8 Usage scenarios in modern systems
9 Collision resolution Theory vs. practice
10 Hash tables for distributed systems Consistent hashing
11 Adding a new noderesource
12 Approximate membership Bloom and quotient filters
13 A simple implementation
14 A bit of theory
15 Bloom filter adaptations and alternatives
16 Understanding metadata bits
17 Python code for lookup
18 Comparison between Bloom filters and quotient filters
19 Frequency estimation and count-min sketch
20 Update
21 Error vs. space in count-min sketch
22 Range queries with count-min sketch
23 Cardinality estimation and HyperLogLog
24 HyperLogLog incremental design
25 LogLog
26 Use case Catching worms with HLL
27 The effect of the number of buckets (m)
28 Part 2. Real-time analytics
29 Streaming data Bringing everything together
30 Streaming data system A meta example
31 Deduplication
32 Practical constraints and concepts in data streams
33 Math bit Sampling and estimation
34 Biased sampling strategy
35 Sampling from data streams
36 Reservoir sampling
37 Biased reservoir sampling
38 Sampling from a sliding window
39 Priority sampling
40 Sampling algorithms comparison
41 Approximate quantiles on data streams
42 Approximate quantiles
43 T-digest How it works
44 Scale functions
45 Merging t-digests
46 Q-digest
47 Quantile queries with q-digests
48 Part 3. Data structures for databases and external memory algorithms
49 Introducing the external memory model
50 Example 1 Finding a minimum
51 Example 2 Binary search
52 Optimal searching
53 External memory model Simple or simplistic
54 Data structures for databases B-trees, Bε-trees, and LSM-trees
55 Data structures in this chapter
56 B-tree balancing
57 Delete
58 Math bit Why are B-tree lookups optimal in external memory
59 Bε-trees
60 Lookups
61 Log-structured merge-trees (LSM-trees)
62 LSM-tree cost analysis
63 External memory sorting
64 Challenges of sorting in external memory An example
65 External memory merge-sort (MB-way merge-sort)
66 What about external quick-sort
67 Finding good enough pivots