Beyond Streaming: Frugal streaming

In streaming, we have a nice model: compute things in one pass with polylog space. I have been thinking about how to go beyond, can some of these things be computed using much less space? I call this "frugal streaming". Qiang Ma, Mark Sandler and I wrote  a paper on frugal streaming for quantiles. I could reference the paper, but akblog has a great entry that not only describes the algorithms in the paper, but --- in their typical style --- also provides a web interface to simulate them! Very cool.