What are probabilistic data structures?

algorithm data-structures probability
free_easy picture free_easy · Dec 5, 2014 · Viewed 12.1k times · Source

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

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

Answer

Severin Pappadeux picture Severin Pappadeux · Dec 5, 2014

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/

Related questions

Data structure for loaded dice?

Suppose that I have an n-sided loaded die where each side k has some probability pk of coming up when I roll it. I'm curious if there is good algorithm for storing this information statically (i.e. for a fixed …

Read More
How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More