Algorithms and Data Structures for Massive Datasets

Algorithms and Data Structures for Massive Datasets

by Emin Tahirovic, Ines Dedovic, Dzejla Medjedovic
Released July 2022
Publisher(s): Manning Publications
ISBN: 9781617298035

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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

Table of contents

  1. title
  2. Copyright
  3. contents
  4. front matter
    1. preface
    2. acknowledgments
    3. about this book
      1. Who should read this book
      2. How this book is organized: A road map
      3. About the code
      4. liveBook discussion forum
    4. about the authors
    5. about the cover illustration
  5. 1 Introduction
    1. 1.1 An example
      1. 1.1.1 An example: How to solve it
      2. 1.1.2 How to solve it, take two: A book walkthrough
    2. 1.2 The structure of this book
    3. 1.3 What makes this book different and whom it is for
    4. 1.4 Why is massive data so challenging for today’s systems?
      1. 1.4.1 The CPU memory performance gap
      2. 1.4.2 Memory hierarchy
      3. 1.4.3 Latency vs. bandwidth
      4. 1.4.4 What about distributed systems?
    5. 1.5 Designing algorithms with hardware in mind
    6. Summary
  6. Part 1 Hash-based sketches
  7. 2 Review of hash tables and modern hashing
    1. 2.1 Ubiquitous hashing
    2. 2.2 A crash course on data structures
    3. 2.3 Usage scenarios in modern systems
      1. 2.3.1 Deduplication in backup/storage solutions
      2. 2.3.2 Plagiarism detection with MOSS and Rabin-Karp fingerprinting
    4. 2.4 O(1)—What's the big deal?
    5. 2.5 Collision resolution: Theory vs. practice
    6. 2.6 Usage scenario: How Python’s dict does it
    7. 2.7 MurmurHash
    8. 2.8 Hash tables for distributed systems: Consistent hashing
      1. 2.8.1 A typical hashing problem
      2. 2.8.2 Hashring
      3. 2.8.3 Lookup
      4. 2.8.4 Adding a new node/resource
      5. 2.8.5 Removing a node
      6. 2.8.6 Consistent hashing scenario: Chord
      7. 2.8.7 Consistent hashing: Programming exercises
    9. Summary
  8. 3 Approximate membership: Bloom and quotient filters
    1. 3.1 How it works
      1. 3.1.1 Insert
      2. 3.1.2 Lookup
    2. 3.2 Use cases
      1. 3.2.1 Bloom filters in networks: Squid
      2. 3.2.2 Bitcoin mobile app
    3. 3.3 A simple implementation
    4. 3.4 Configuring a Bloom filter
      1. 3.4.1 Playing with Bloom filters: Mini experiments
    5. 3.5 A bit of theory
      1. 3.5.1 Can we do better?
    6. 3.6 Bloom filter adaptations and alternatives
    7. 3.7 Quotient filter
      1. 3.7.1 Quotienting
      2. 3.7.2 Understanding metadata bits
      3. 3.7.3 Inserting into a quotient filter: An example
      4. 3.7.4 Python code for lookup
      5. 3.7.5 Resizing and merging
      6. 3.7.6 False positive rate and space considerations
    8. 3.8 Comparison between Bloom filters and quotient filters
    9. Summary
  9. 4 Frequency estimation and count-min sketch
    1. 4.1 Majority element
      1. 4.1.1 General heavy hitters
    2. 4.2 Count-min sketch: How it works
      1. 4.2.1 Update
      2. 4.2.2 Estimate
    3. 4.3 Use cases
      1. 4.3.1 Top-k restless sleepers
      2. 4.3.2 Scaling the distributional similarity of words
    4. 4.4 Error vs. space in count-min sketch
    5. 4.5 A simple implementation of count-min sketch
      1. 4.5.1 Exercises
      2. 4.5.2 Intuition behind the formula: Math bit
    6. 4.6 Range queries with count-min sketch
      1. 4.6.1 Dyadic intervals
      2. 4.6.2 Update phase
      3. 4.6.3 Estimate phase
      4. 4.6.4 Computing dyadic intervals
    7. Summary
  10. 5 Cardinality estimation and HyperLogLog
    1. 5.1 Counting distinct items in databases
    2. 5.2 HyperLogLog incremental design
      1. 5.2.1 The first cut: Probabilistic counting
      2. 5.2.2 Stochastic averaging, or “when life gives you lemons”
      3. 5.2.3 LogLog
      4. 5.2.4 HyperLogLog: Stochastic averaging with harmonic mean
    3. 5.3 Use case: Catching worms with HLL
    4. 5.4 But how does it work? A mini experiment
      1. 5.4.1 The effect of the number of buckets (m)
    5. 5.5 Use case: Aggregation using HyperLogLog
    6. Summary
  11. Part 2 Real-time analytics
  12. 6 Streaming data: Bringing everything together
    1. 6.1 Streaming data system: A meta example
      1. 6.1.1 Bloom-join
      2. 6.1.2 Deduplication
      3. 6.1.3 Load balancing and tracking the network traffic
    2. 6.2 Practical constraints and concepts in data streams
      1. 6.2.1 In real time
      2. 6.2.2 Small time and small space
      3. 6.2.3 Concept shifts and concept drifts
      4. 6.2.4 Sliding window model
    3. 6.3 Math bit: Sampling and estimation
      1. 6.3.1 Biased sampling strategy
      2. 6.3.2 Estimation from a representative sample
    4. Summary
  13. 7 Sampling from data streams
    1. 7.1 Sampling from a landmark stream
      1. 7.1.1 Bernoulli sampling
      2. 7.1.2 Reservoir sampling
      3. 7.1.3 Biased reservoir sampling
    2. 7.2 Sampling from a sliding window
      1. 7.2.1 Chain sampling
      2. 7.2.2 Priority sampling
    3. 7.3 Sampling algorithms comparison
      1. 7.3.1 Simulation setup: Algorithms and data
    4. Summary
  14. 8 Approximate quantiles on data streams
    1. 8.1 Exact quantiles
    2. 8.2 Approximate quantiles
      1. 8.2.1 Additive error
      2. 8.2.2 Relative error
      3. 8.2.3 Relative error in the data domain
    3. 8.3 T-digest: How it works
      1. 8.3.1 Digest
      2. 8.3.2 Scale functions
      3. 8.3.3 Merging t-digests
      4. 8.3.4 Space bounds for t-digest
    4. 8.4 Q-digest
      1. 8.4.1 Constructing a q-digest from scratch
      2. 8.4.2 Merging q-digests
      3. 8.4.3 Error and space considerations in q-digests
      4. 8.4.4 Quantile queries with q-digests
    5. 8.5 Simulation code and results
    6. Summary
  15. Part 3 Data structures for databases and external memory algorithms
  16. 9 Introducing the external memory model
    1. 9.1 External memory model: The preliminaries
    2. 9.2 Example 1: Finding a minimum
      1. 9.2.1 Use case: Minimum median income
    3. 9.3 Example 2: Binary search
      1. 9.3.1 Bioinformatics use case
      2. 9.3.2 Runtime analysis
    4. 9.4 Optimal searching
    5. 9.5 Example 3: Merging K sorted lists
      1. 9.5.1 Merging time/date logs
      2. 9.5.2 External memory model: Simple or simplistic?
    6. 9.6 What’s next
    7. Summary
  17. 10 Data structures for databases: B-trees, Bε-trees, and LSM-trees
    1. 10.1 How indexing works
    2. 10.2 Data structures in this chapter
    3. 10.3 B-trees
      1. 10.3.1 B-tree balancing
      2. 10.3.2 Lookup
      3. 10.3.3 Insert
      4. 10.3.4 Delete
      5. 10.3.5 B+-trees
      6. 10.3.6 How operations on a B+-tree are different
      7. 10.3.7 Use case: B-trees in MySQL (and many other places)
    4. 10.4 Math bit: Why are B-tree lookups optimal in external memory?
      1. 10.4.1 Why B-tree inserts/deletes are not optimal in external memory
    5. 10.5 Bε-trees
      1. 10.5.1 Bε-tree: How it works
      2. 10.5.2 Buffering mechanics
      3. 10.5.3 Inserts and deletes
      4. 10.5.4 Lookups
      5. 10.5.5 Cost analysis
      6. 10.5.6 Bε-tree: The spectrum of data structures
      7. 10.5.7 Use case: Bε-trees in TokuDB
      8. 10.5.8 Make haste slowly, the I/O way
    6. 10.6 Log-structured merge-trees (LSM-trees)
      1. 10.6.1 The LSM-tree: How it works
      2. 10.6.2 LSM-tree cost analysis
      3. 10.6.3 Use case: LSM-trees in Cassandra
    7. Summary
  18. 11 External memory sorting
    1. 11.1 Sorting use cases
      1. 11.1.1 Robot motion planning
      2. 11.1.2 Cancer genomics
    2. 11.2 Challenges of sorting in external memory: An example
      1. 11.2.1 Two-way merge-sort in external memory
    3. 11.3 External memory merge-sort (M/B-way merge-sort)
      1. 11.3.1 Searching and sorting in RAM vs. external memory
    4. 11.4 What about external quick-sort?
      1. 11.4.1 External memory two-way quick-sort
      2. 11.4.2 Toward external memory multiway quick-sort
      3. 11.4.3 Finding enough pivots
      4. 11.4.4 Finding good enough pivots
      5. 11.4.5 Putting it all back together
    5. 11.5 Math bit: Why is external memory merge-sort optimal?
    6. 11.6 Wrapping up
    7. Summary
  19. references
  20. index
  21. inside back cover

Product information

  • Title: Algorithms and Data Structures for Massive Datasets
  • Author(s): Emin Tahirovic, Ines Dedovic, Dzejla Medjedovic
  • Release date: July 2022
  • Publisher(s): Manning Publications
  • ISBN: 9781617298035