Probabilistic algorithms: what are they and where can I find a complete list of them?

Question

Algorithms

Here is an example:
Bloom filter
or
Markov chains
And where can I see a complete list of such developments?
Interested primarily in the problem of storage, clustering and classification of information.

Answer 1

Here I will collect links to probabilistic algorithms:
1. Bloom filter https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D...
2. MinHash habrahabr.ru/post/ 115147
3. LogLog: find the number of unique elements -- habrahabr.ru/post/119852
3.1 HyperLogLog
4. Search for similar documents with MinHash + LHS: habrahabr.ru/post/250673
5. https://en.wikipedia.org/wiki /Count%E2%80%93min_sketch -- approximate collection of event frequencies in the stream.
6. Algorithm Rabin - Karp: search for substrings in a string through hashing. https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...
https://en.wikipedia.org/wiki/Category:Probabilist...

Answer 2

In fact, many algorithms are probabilistic in nature. Even TCP and UDP packets have a checksum, which helps to find an error only with some (rather large) probability. You can also look at distributed algorithms from the same series - Gossip, Raft, and so on. From less network - compression algorithms (with and without losses), genetic algorithms , neural networks.

Answer 3

there is such a place:
discopal.ispras.ru/%D0%91%D0%BB%D0%BE%D0%B3:Advanc...
in general, this is a page of one course in the Moscow Phystech, among the materials there is something about probabilistic algorithms