What is the canonical reference on probabilistic data structures?

Question

I've heard of probabilistic data structures like Skip Lists and Bloom Filters being immensely useful and I'd like to learn more about them in general. Is there a canonical reference on the subject on the level of Cormen et al.?

Answer 1

The closest site I can think of that might be canonical is the NIST standards web site:

http://xlinux.nist.gov/dads/HTML/skiplist.html

This site can be short on descriptions but has links to external sites ..

Answer 2

The best list that I could find, that has probabilistic data structures is this Wikipedia page. The problem here is, the page also includes probabilistic algorithms. The list that I know of is:

• Bloom Filter
• Random Tree - This is a general term, and "umbrellas" many different structures.
• Skip List
• Treap

There are probably many more, but these are the ones that I have found or that I was aware of.