  Histograms, i.e., piece-wise constant approximations, are a popular tool used
to represent data distributions. Traditionally, the difference between the
histogram and the underlying distribution (i.e., the approximation error) is
measured using the $L_p$ norm, which sums the differences between the two
functions over all items in the domain. Although useful in many applications,
the drawback of this error measure is that it treats approximation errors of
all items in the same way, irrespective of whether the mass of an item is
important for the downstream application that uses the approximation. As a
result, even relatively simple distributions cannot be approximated by succinct
histograms without incurring large error.
  In this paper, we address this issue by adapting the definition of
approximation so that only the errors of the items that belong to the support
of the distribution are considered. Under this definition, we develop efficient
1-pass and 2-pass streaming algorithms that compute near-optimal histograms in
sub-linear space. We also present lower bounds on the space complexity of this
problem. Surprisingly, under this notion of error, there is an exponential gap
in the space complexity of 1-pass and 2-pass streaming algorithms. Finally, we
demonstrate the utility of our algorithms on a collection of real and synthetic
data sets.
