Polynomial Histograms for Memory-Efficient Representation of Long-tailed System Distributions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910270660542464 |
|---|---|
| author | Stokely, Murray Hesterberg, Tim Merchant, Arif Coehlo, Nate |
| author_facet | Stokely, Murray Hesterberg, Tim Merchant, Arif Coehlo, Nate |
| contents | Distributed systems must frequently keep track of many different types of performance metrics across many different computers. For example, the latency distribution of certain operations may be computed for a large combination of computers, users, and operations. These empirical distributions need to be collected at minimal expense on the individual software components, efficiently aggregated across multiple dimensions, and stored in a compact representation for a variety of downstream data analysis applications.
We describe an information loss metric for binned data that allows us to optimize cost of information loss from different histogram representations. We explore the use of polynomial histograms where each bin of a histogram is annotated with moments of the underlying distribution in that bin. These polynomial histograms are compared to traditional histograms using the same storage cost for additional bins instead of annotations in each bin. We describe an application of these techniques for file system metrics for a large production system, and analytically characterize when polynomial histograms offer more information at lower cost. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_30360 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polynomial Histograms for Memory-Efficient Representation of Long-tailed System Distributions Stokely, Murray Hesterberg, Tim Merchant, Arif Coehlo, Nate Distributed, Parallel, and Cluster Computing Applications 62B10 G.4; H.3.2 Distributed systems must frequently keep track of many different types of performance metrics across many different computers. For example, the latency distribution of certain operations may be computed for a large combination of computers, users, and operations. These empirical distributions need to be collected at minimal expense on the individual software components, efficiently aggregated across multiple dimensions, and stored in a compact representation for a variety of downstream data analysis applications. We describe an information loss metric for binned data that allows us to optimize cost of information loss from different histogram representations. We explore the use of polynomial histograms where each bin of a histogram is annotated with moments of the underlying distribution in that bin. These polynomial histograms are compared to traditional histograms using the same storage cost for additional bins instead of annotations in each bin. We describe an application of these techniques for file system metrics for a large production system, and analytically characterize when polynomial histograms offer more information at lower cost. |
| title | Polynomial Histograms for Memory-Efficient Representation of Long-tailed System Distributions |
| topic | Distributed, Parallel, and Cluster Computing Applications 62B10 G.4; H.3.2 |
| url | https://arxiv.org/abs/2605.30360 |