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.

Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications.

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.

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

Ebook License

End-User Warranty And License Agreement

1. Grant Of License

Manning Has Authorized The Download By You Of An Unrestricted Number Of Copies Of The Electronic Book (Ebook) In Any Of The Available Formats. Manning Grants You A Nonexclusive, Nontransferable License To Use The Ebook According To The Terms And Conditions Herein. This License Agreement Permits You To Install The Ebook On Any And All Your Devices For Your Personal Use Only.

2. Restrictions

You Shall Not: (1) Share, Resell, Rent, Assign, Timeshare, Distribute, Or Transfer All Or Part Of The Ebook Or Any Rights Granted Hereunder To Any Other Person; (2) Duplicate The Ebook, Except For A Single Backup Or Archival Copy; (3) Remove Any Proprietary Notices, Labels, Or Marks From The Ebook; (4) Transfer Or Sublicense Title To The Ebook To Any Other Party.

3. Intellectual Property Protection

The Ebook Is Owned By Manning And Is Protected By United States And International Copyright And Other Intellectual Property Laws. Manning Reserves All Rights In The Ebook Not Expressly Granted Herein. This License And Your Right To Use The Ebook Terminate Automatically If You Violate Any Part Of This Agreement. In The Event Of Termination, You Must Remove The Original And Any Copies Of The Ebook From All Your Devices.

4. Source Code Supplementary Material

Any Source Code Files Provided As A Supplement To The Book Are Freely Available To The Public For Download. Reuse Of The Code Is Permitted, In Whole Or In Part, Including The Creation Of Derivative Works, Provided That You Acknowledge That You Are Using It And Identify The Source: Title, Publisher And Year.

5. Limited Warranty

Manning Warrants That The Ebook Files, A Copy Of Which You Are Authorized To Download, Are Free From Defects In The Operational Sense That They Can Be Read By A Pdf Reader Or Epub Reader, Or Other. Except For This Express Limited Warranty, Manning Makes And You Receive No Warranties, Express, Implied, Statutory Or In Any Communication With You, And Manning Specifically Disclaims Any Other Warranty Including The Implied Warranty Of Merchantability Or Fitness Or A Particular Purpose. Manning Does Not Warrant That The Operation Of The Ebook Will Be Uninterrupted Or Error Free. If The Ebook Was Purchased In The United States, The Above Exclusions May Not Apply To You As Some States Do Not Allow The Exclusion Of Implied Warranties. In Addition To The Above Warranty Rights, You May Also Have Other Rights That Vary From State To State.

6. Limitation Of Liability

In No Event Will Manning Be Liable For Any Damages, Whether Arising For Tort Or Contract, Including Loss Of Data, Lost Profits, Or Other Special, Incidental, Consequential, Or Indirect Damages Arising Out Of The Use Or Inability To Use The Ebook.

7. General

This Agreement Constitutes The Entire Agreement Between You And Manning And Supersedes Any Prior Agreement Concerning The Ebook. This Agreement Is Governed By The Laws Of The State Of New York.