Practical algorithms for self scaling histograms or better than average data collection

The intended goal of these algorithms is to facilitate the change of the most common method of quick-and-dirty metering from simple (but possibly misleading) averages to more informative histograms.

Abstract

Abstract This paper presents practical algorithms for implementing self-scaling histograms. We show that these algorithms can deal well with observations drawn from either continuous or discrete distributions, have fixed storage and low computational overhead, and can faithfully capture the distribution of the data with very low error. As a tool for intrusive large-scale performance measurement, histograms are the ideal compromise between practical limitations (storage, computational cost, interference with the system being measured) and the desire for a complete record of all observations. In practice they are infrequently used because histograms are perceived as cumbersome to use, and it is often hard to decide in advance on appropriate parameters (bucket sizes, range). Use of programming language technology (object-oriented techniques for example) can solve the first problem, and the algorithms presented here can solve the second. The intended goal of these algorithms is to facilitate the change of the most common method of quick-and-dirty metering from simple (but possibly misleading) averages to more informative histograms.