31

I have read about "probabilistic" data structures like bloom filters and skip lists.

What are the common characteristics of probabilistic data structures and what are they used for?

Improve this question

5 Answers 5

Reset to default
26

There are probably a lot of different (and good) answers, but in my humble opinion, the common characteristics of probabilistic data structures is that they provide you with approximate, not precise answer.

How many items are here? About 1523425 with probability of 99%

Update: Quick search produced link to decent article on the issue:

https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/

Improve this answer
3
  • 1
    Isn't a hashtable without a linkedlist in each slot (thus storing only a "yes item exist" or "no item don't exist" in each slot) also a probabilistic data structure?
    – Pacerier
    May 6, 2017 at 14:02
  • 2
    @Pacerier, what you are saying is actually a bloom filter with k=1 hash function. But as it can certainly say that if an item is 'not exists', it can't certainly say that if the item 'exists'. That's why, yes, it will be a probabilistic data structure.
    – sha-1
    Dec 3, 2017 at 8:45
  • 1
    Skip list can be treated as a probabilistic structure but it gives an exact answer. In this case probability affects performance but not correctness.
    – freakish
    Sep 12, 2018 at 8:18
23

If you are interested in probabilistic data structures, you might want to read my recently published book "Probabilistic Data Structures and Algorithms for Big Data Applications" (ISBN: 9783748190486, available at Amazon) where I have explained many of such space-efficient data structures and fast algorithms that are extremely useful in modern Big Data applications.

In this book, you can find the state of the art algorithms and data structures that help to handle such common problems in Big Data processing as

  • Membership querying (Bloom filter, Counting Bloom filter, Quotient filter, Cuckoo filter).
  • Cardinality (Linear counting, probabilistic counting, LogLog, HyperLogLog, HyperLogLog++).
  • Frequency (Majority algorithm, Frequent, Count Sketch, Count-Min Sketch).
  • Rank (Random sampling, q-digest, t-digest).
  • Similarity (LSH, MinHash, SimHash).

You can get a free preview and all related information about the book at https://pdsa.gakhov.com

Improve this answer
20

Probabilistic data structures can't give you a definite answer, instead they provide you with a reasonable approximation of the answer and a way to approximate this estimation. They are extremely useful for big data and streaming application because they allow to dramatically decrease the amount of memory needed (in comparison to data structures that give you exact answers).

In majority of the cases these data structures use hash functions to randomize the items. Because they ignore collisions they keep the size constant, but this is also a reason why they can't give you exact values. The advantages they bring:

  • they use small amount of memory (you can control how much)
  • they can be easily parallelizable (hashes are independent)
  • they have constant query time (not even amortized constant like in dictionary)

Frequently used probabilistic data structures are:

Improve this answer
3

There is a list of probabilistic data structures in wikipedia for your reference: https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures

There are different definitions about what "probabilistic data structure" is. IMHO, probabilistic data structure means that the data structure uses some randomized algorithm or takes advantage of some probabilistic characteristics internally, but they don't have to behave probabilistically or un-deterministically from the data structure user's perspective.

  • There are many "probabilistic data structures" with probabilistically behavior such as the bloom filter and HyperLogLog mentioned by the other answers.

  • At the same time, there are other "probabilistic data structures" with determined behavior (from a user's perspective) such as skip list. For skip list, users can use it similarly as a balanced binary search tree but is implemented with some probability related idea internally. And according to skip list's author William Pugh:

    Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

Improve this answer
2
  • I don't believe that Skip Lists are probabilistic data structures. They are guaranteed to give the correct result, and there is no error rate unlike true probabilistic data structures like Bloom Filters or HyperLogLog. Interestingly, the linked Wikipedia article has a hyperlink on "probabilistic" which leads to the Wikipedia article for "Randomized Algorithms", a totally unrelated topic. This calls into question the validity of the linked Wikipedia page.
    – Shuklaswag
    Jul 8, 2018 at 14:35
  • @Shuklaswag Define "true probabilistic data structure" or even "probabilistic data structure". I disagree with you. Even though skip lists always give correct answers the probability is an essential part of the algorithm that makes it useful.
    – freakish
    Sep 12, 2018 at 8:24
0

Probabilistic data structures allow for constant memory space and extremely fast processing while still maintaining a low error rate with a specified degree on uncertainity.

Some use-cases are

  • Checking presence of value in a data set
  • Frequency of events
  • Estimate approximate size of a data set
  • Ranking and grouping
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.