  Modern applications require processing streams of data for estimating
statistical quantities such as quantiles with small amount of memory. In many
such applications, in fact, one needs to compute such statistical quantities
for each of a large number of groups, which additionally restricts the amount
of memory available for the stream for any particular group. We address this
challenge and introduce frugal streaming, that is algorithms that work with
tiny -- typically, sub-streaming -- amount of memory per group.
  We design a frugal algorithm that uses only one unit of memory per group to
compute a quantile for each group. For stochastic streams where data items are
drawn from a distribution independently, we analyze and show that the algorithm
finds an approximation to the quantile rapidly and remains stably close to it.
We also propose an extension of this algorithm that uses two units of memory
per group. We show with extensive experiments with real world data from HTTP
trace and Twitter that our frugal algorithms are comparable to existing
streaming algorithms for estimating any quantile, but these existing algorithms
use far more space per group and are unrealistic in frugal applications;
further, the two memory frugal algorithm converges significantly faster than
the one memory algorithm.
