This blog post is a nice survey about other interesting probabilistic data structures: http://highlyscalable.wordpress.com/2012/05/01/probabilistic...