Search code examples
algorithmdata-structuresprobability

What are probabilistic data structures?

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?

Solution

  • 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/