Menu
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?
736
In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs.
Probabilistic data is information that is based on relational patterns and the likelihood of a certain outcome. A common example of probabilistic data at use is in weather forecasting, where a value is based off of past conditions and probability.
A probabilistic algorithm A is an algorithm whose behavior is partly con- trolled by random events. The computation of the output y on input x de- pends on the outcome of a finite number of random experiments. In partic- ular, applying A to the same input x twice may yield two different outputs.
Instead of limiting analysis to best case or worst case, we can analyze all cases based on a distribution of the probability of each case and compute the expected runtime based on this distribution.
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/
146
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
