1. A system, comprising: a network-based service implemented by a plurality of computers, wherein the network-based service is configured to provide one or more services to a plurality of clients over a network; a performance monitor implemented on one or more computers configured to: monitor one or more dimensions of the network-based service with regard to one or more performance metrics, wherein each dimension comprises a predetermined portion of the plurality of computers, and wherein each performance metric represents an aggregate performance of a respective portion of computers of a respective dimension with respect to the network-based service processing one or more requests; and record the one or more performance metrics of the network-based service as performance data; and a performance data aggregator implemented on one or more computers configured to: parse the performance data for at least one particular performance metric of the one or more performance metrics and at least one particular dimension of the one or more dimensions; create a histogram representation data structure corresponding to a sparse exponential histogram representation of the parsed performance data, wherein empty buckets of the sparse exponential histogram representation are omitted in the histogram representation data structure; and transmit or store the histogram representation data structure for subsequent analysis.