  One of the most common statistics computed over data elements is the number
of distinct keys. A thread of research pioneered by Flajolet and Martin three
decades ago culminated in the design of optimal approximate counting sketches,
which have size that is double logarithmic in the number of distinct keys and
provide estimates with a small relative error. Moreover, the sketches are
composable, and thus suitable for streamed, parallel, or distributed
computation.
  We consider here all statistics of the frequency distribution of keys, where
a contribution of a key to the aggregate is concave and grows (sub)linearly
with its frequency. These fundamental aggregations are very common in text,
graphs, and logs analysis and include logarithms, low frequency moments, and
capping statistics.
  We design composable sketches of double-logarithmic size for all concave
sublinear statistics. Our design combines theoretical optimality and practical
simplicity. In a nutshell, we specify tailored mapping functions of data
elements to output elements so that our target statistics on the data elements
is approximated by the (max-) distinct statistics of the output elements, which
can be approximated using off-the-shelf sketches. Our key insight is relating
these target statistics to the {\em complement Laplace} transform of the input
frequencies.
