Nice slides. You should check out https://github.com/twitter/algebird - we've implemented a number of streaming algorithms (HyperLogLog, Count Min Sketch, along with stuff like minhash and bloom filters) in Scala as Monoid typeclasses. Love to hear your thoughts or get your contributions.
Note that you can do a lot with streaming algorithms (it's not just counting). Also the reduced memory usage (orders of magnitude) makes the complexity of random writes not such a problem as you have less need to go outside a single machine.
[1] Slides on streaming algorithms: http://noelwelsh.com/streaming-algorithms/2012/11/22/streami...