Probabilistic
Data Structures and Algorithms
for Big Data Applications

A technical book about popular space-efficient data structures and fast algorithms that are extremely useful in modern Big Data applications.

ISBN: 978-3748190486 Paperback: 220 pages

Table of Contents Where to buy Follow @gakhov

The best Probabilistic Algorithms ebooks of all time

About the book

Probabilistic data structures is a common name for data structures based mostly on different hashing techniques. Unlike regular (or deterministic) data structures, they always provide approximated answers but with reliable ways to estimate possible errors. Fortunately, the potential losses or errors are fully compensated for by extremely low memory requirements, constant query time, and scaling, three factors that become important in Big Data applications.

While it is impossible to cover all the existing amazing solutions, this book is to highlight their common ideas and important areas of application, including membership querying, counting, stream mining, and similarity estimation.

The purpose of this book is to introduce technology practitioners, including software architects and developers, as well as technology decision makers to probabilistic data structures and algorithms. Reading this book, you will get a theoretical and practical understanding of probabilistic data structures and learn about their common uses.

  •  Learn how to solve practical issues of massive data handling
  •  Master the theoretical aspects of probabilistic data structures
  •  Identify the right data structures for your particular problems

This is not a book for scientists, but to gain the most out of it you will need to have basic mathematical knowledge and an understanding of the general theory of data structures and algorithms.

Table Of Contents

Hashing

We give a brief overview of popular hash functions and hash tables that are widely used in probabilistic data structures.

  • Cryptographic hash functions
  • Non-Cryptographic hash functions
  • Hash tables

Membership

We study the most well-known known probabilistic data structures that are used to answer approximate membership queries.

  • Bloom filter
  • Counting Bloom filter
  • Quotient filter
  • Cuckoo filter

Cardinality

We learn data structures that allow to estimate the number of unique elements in a dataset.

  • Linear Counting
  • Probabilistic Counting
  • LogLog and HyperLogLog

Frequency

We discuss solutions for common problems in streaming applications, such as finding frequency of some element, filtering most frequent elements in the stream, detecting trending elements, etc.

  • Majority algorithm
  • Frequent algorithm
  • Count Sketch
  • Count–Min Sketch

Rank

We study data structures to estimate quantiles and percentiles in a data stream using only one pass through the data.

  • Random sampling
  • q-digest
  • t-digest

Similarity

We learn how to effciently solve the nearest neighbor problem for large datasets using sub-linear in time solutions.

  • Locality-Sensitive hashing
  • MinHash
  • SimHash

Andrii Gakhov, Ph.D.

Andrii Gakhov is a mathematician and software engineer holding a Ph.D.in mathematical modeling and numerical methods. He has been a teacher in the School of Computer Science at V. Karazin Kharkiv National University in Ukraine for a number of years and currently works as a software practitioner for ferret go GmbH, the leading community moderation, automation, and analytics company in Germany. His fields of interests include machine learning, stream mining, and data analysis.

Where to buy

Paperback edition
Published by BoD

Country Store Link
America
 United States Amazon.com Visit
 Canada Amazon.ca Visit
 Mexico Amazon.com.mx Visit
 Brazil Amazon.com.br Visit
Europe
 United Kingdom Amazon.co.uk Visit
 Germany BoD (Verlag) Visit
Thalia Visit
Amazon.de Visit
 Austria BoD (Verlag) Visit
Amazon.de Visit
 France Amazon.fr Visit
 Spain Amazon.es Visit
 Italy Amazon.it Visit
 Netherlands BoD (Verlag) Visit
Asia
 India Amazon.in Visit
 Japan Amazon.co.jp Visit
Oceania
 Australia Amazon.com.au Visit
BoD Publisher delivers  to all EU countires for FREE.

E-book edition
Exclusively at Amazon

Country Store Link
America
 United States Amazon.com Visit
 Canada Amazon.ca Visit
 Mexico Amazon.com.mx Visit
 Brazil Amazon.com.br Visit
Europe
 United Kingdom Amazon.co.uk Visit
 Germany Amazon.de Visit
 Austria Amazon.de Visit
 France Amazon.fr Visit
 Spain Amazon.es Visit
 Italy Amazon.it Visit
 Netherlands Amazon.nl Visit
Asia
 India Amazon.in Visit
 Japan Amazon.co.jp Visit
Oceania
 Australia Amazon.com.au Visit

Get a free preview
This book on Google Books


Download Download

Errata

If you have found any error that is not in the list below, please contact us by email pdsa@gakhov.com. As soon as the error is confirmed and fixed, its description will appear in this section (details are omitted in mobile view due to space restrictions).

Edition Location Original text Corrected text
[paperback] p. 31 "... by bitwise XOR, however ..." "... by bitwise AND, however ..."
[paperback] p. 62, Example 3.1 "... of unique elements is 23 GB." "... of unique elements is 2.3 GB."
[paperback] p. 81, Formula 3.12 $$\hat n \approx \alpha_{m}\cdot m^{2} \cdot \left(\sum_{j=0}^{m-1}2^{-COUNTER[j]}\right)$$ $$\hat n \approx \alpha_{m}\cdot m^{2} \cdot \left(\sum_{j=0}^{m-1}2^{-COUNTER[j]}\right)^{-1}$$
[paperback] p. 174, Example 6.8 $$c(d_1, d_4) = \frac{255 \cdot 0 + 0 \cdot 191 + 0 \cdot 255}{255 \cdot 255} = 0$$ $$c(d_1, d_4) = \frac{255 \cdot 0 + 0 \cdot 191 + 0 \cdot 255}{\sqrt{255^{2} + 0^2 + 0^2} \cdot \sqrt{0^{2} + 191^2 + 255^2}} = 0$$