OTEP 149 Base-2 Exponential Histogram prototypes

Logarithm histogram mapper

The file logarithm.go demonstrates an implementation of the base-2 exponential histogram based on the built-in logarithm function.

LookupTable histogram mapper

The file lookuptable.go demonstrates an implementation of the OTEP base-2 exponential histogram based on a precomputed table of constants.

Generate a constants table

The constants table for the LookupTable histogram mapper is not checked-in. The constants table can be used by any scale of histogram less than or equal to the maximum scale computed. To generate a constants table, run:

go run ./generate MAXSCALE

For some value of MAXSCALE. Note that the generated table will contain 2**MAXSCALE entries, where ** represents exponentiation (i.e., two to the power of MAXSCALE). Practical limits start to apply around MAXSCALE=16, where this program takes weeks of CPU time to run.

Acknowledgements

Yuke Zhuge and Otmar Ertl are the primary authors of these prototypes. See NrSketch and DynaHist repositories for more detail.