Notes on the demo

The demo uses 20 quantiles internally and 40 data points to generate the initial histogram. Since the initial histograms are calculated "looking back" in time there seems to be a time difference between the mean value and the median value. This is compensated for by shifting the quantile data by 20 time values compared to the values in linear time and the mean data. Uncheck x-shift to see the effect. It is only used for the display and has no effect on the underlying data.

When changing the display properties, only the quantiles displayed are changed, in the background it is still 20 quantiles (equaling 21 values including minimum (the zeroth quantile) and the maximum (the 20th quantile)).

The calculation of the outer quantiles from a low number of data points is problematic. This is the reason why 40 points are used to calculate 20 quantiles. When displaying 10 quantiles with the uniform noise generator, they should converge toward 0.1, 0.2, ..., 0.9. and the median and mean values should be identical. In this demo there is still a small difference noticeable. For displaying rough data like CPU load, however, it should be good enough. When absolute precision is needed, it may be necessary to really store all data points and calculate the quantiles based on all data points (provided, enough storage and processing power is available).

Data structures

The following data structures are of importance:

• The quantiles are represented by an array q which includes minimum and maximum.
  • N quantiles therefore are represented by N+1 values.
• The histograms are represented by the corresponding values v and a density or step height d.
  • When two succeding values of v are different, the corresponding value of d represents the density between these values.
  • When two succeding values of v are equal, the corresponding value of d represents the height of the step.
  • The difference between q and v is only in the interpretation.
    • When converting quantiles q to the corresponding v and d values, v=q and d is adjusted that the integral between two succeeding values of v is equal and the integral over the whole distribution function is 1.
• A data structure log_data to hold the configuration and the values
  • The configuration consists of
    • num_quantiles : 20
      • The number of quantiles.
    • num_quantiles_first : 40
      • The number of quantiles for calculating the first histogram when inserting a data point which is then resampled to num_quantiles.
    • division_factor : 2
      • The number of values which are combined when going to the next level.
    • num_levels : 40
      • The number of levels where data values are combined.
    • linear_num_keep : 200
      • The number of data points to keep at the first (linear) level.
    • level_num_keep : 10
      • The number of data points to keep in each level before combining the oldest.
  • The levels contain
    • x
      • A vector with the x-values.
      • Upon combining they are averaged.
    • y
      • A vector containing the y-values.
      • Upon combining they are averaged.
      • The first level contains the inserted data points. The later levels contain the mean values.
    • quantiles_with_minmax
      • The quantiles including the minimum as first value and the maximum as last value.

Illustrations

The following figures illustrate the operations on the histograms.

Figure 1: A time signal with 9 points.

Figure 2: The time signal is sorted and used as q-values. The q-values are then used to calculate the histogram. The v-values are equal to the q-values and d-values are calculated accordingly. Between each pair of succeeding v-values 1/9th of the total density is assigned.

Figure 3: The integral over d results in the distribution function. It ranges from 0 to 1. Between equal v-values, a step with a height of 1/9th is present. Between different v-values a slope with the according steepness is present such that the integral increases by 1/9th for every value.

Figure 4: From the integral, a new set of q-values is derived. Here, 5 quantiles are taken from the histogram. The resulting q-vector consists of the minimum, 4 intermediate values and the maximum. This q-vector can also contain multiple entries with the same value when steps are present.

Figure 5: The addition of two histograms. The sum contains all v-values of the two added histograms. The d-values are added for the stretched parts in between different v-values. The integral over the result is 2, therefore it has to be scaled by 0.5 for further processing.

The functions

The function

quantiles_with_minmax_to_normalized_histogram( q ) -> [v,d]

is used to convert an array of quantiles into a histogram. It accomplishes the step when taking the y-values from Fig. 1 as q-values and produces the v-values and d-values in Fig. 2. In the demo, simply 40 values of the time series are taken, sorted, and then converted into a histogram.

In order to obtain the 21 v-values and d-values for 20 quantiles, the resulting histogram is then converted back to q-values. The function

histogram_to_quantiles_with_minmax( v, d, n ) -> q

integrates the histogram and extracts the v-values which correspond to the quantiles. See Fig. 3 and Fig. 4 for this operation.

In order to combine two data points, the quantiles are converted into histograms and added with

add_histograms( v1, d1, v2, d2 ) -> [v,d]

. This operation is illustrated in Fig. 5.

Since the resulting histogram does have an integral of 2, plus some numerical errors, the integral is calculated with

integrate_histogram( v, d ) -> integral

and the histogram is renormalized by scaling

scale_histogram( v, d, a ) -> [v,d]

and then converted back into 20 quantiles using

histogram_to_quantiles_with_minmax( v, d, n ) -> q

.

In order to acutally insert data, the configuration and intermediate values are stored in log_data and

log_insert_datapoint( log_data, x, y )

is called for each data point. (When 1000x is checked in the demo, it is called 10000 times per second.) This modifies log_data and with

get_log_values( log_data ) -> [ x, y, q ]

the vectors and matrices containing the corresponding values are retrieved.

Time scaling

For the time scaling the function

$$ x_{\rm{linlog}}\left(x_{\rm{lin}}\right) = \begin{cases} x_{\rm{lin}} & \text{when} \quad |x_{\rm{lin}}|<x_{\rm{linrange}} \\ x_{\rm{linrange}} * \left( p*\left(\ln\left(x_{\rm{lin}}\right)\right)^{1/p}-(p-1) \right) & \text{else} \end{cases} $$

with $p=10$ is used.

The values on the linlog-axis do not directly correspond to a meaningful quantity outside of the linear range. Automatically setting labels using a uniform grid will be misleading. Instead, the grid and scaling must be set considering the scaling function. In the demo, custom labels for appropriate times are added in the plot according to their linlog-values.