The Histogram Library (histogram)

Module: histograms

View source Contains functions for creating single-column histograms. The histogram is created on the last argument of a given relation and statistics are computed on each bucket of the histogram. By default, min, max, and count statistics are included by all the functions of the module. The supported types of histograms are equi-width and equi-depth. In an equi-width histogram, domain values are bucketized on intervals of equal ranges. In an equi-depth histogram, the buckets have equal size (in terms of the number of tuples contained in the bucket). The equi-depth histograms are constructed on a best-effort basis and do not guarantee an optimal bucketization.

The module offers functions of 2 types with different interfaces:

Hardcoded number of statistic functions

Here, the number of requested statistics is part of the function name, e.g. histogram_equiwidth_2[R, 10, F1, F2] where

• R is a relation
• 10 is the number of buckets
• F1 and F2 are two aggregate statistic functions to be applied to the values of the tuples contained in the bucket, such as average or sum.

The output is a relation with arity $4+i$, where $i$ is the number of requested statistics: (bucket_id, min_value, max_value, count, F1_stat, ..., Fi_stat) where

• bucket_id is an integer identifier for the bucket starting from 1
• min_value is the minimum value among tuples contained in the bucket
• max_value is the maximum value among tuples contained in the bucket
• count is the number of tuples contained in the bucket
• The remaining arguments are the values of the requested statistics, in the order that they were specified.

The maximum supported number of statistic functions that can be requested via this interface is 3.

Example 1

def T = {1; 2; 3; 4; 6; 11}
 
with histograms use histogram_equiwidth_2
 
def output = histogram_equiwidth_2[T, 2, average, sum]
(1, 1, 4, 4, 2.5, 10)
(2, 6, 11, 2, 8.5, 17)

Example 2

def T = {1; 2; 3; 4; 6; 11}
 
with histograms use histogram_equidepth_1
 
def output = histogram_equidepth_1[T, 2, average]
(1, 1, 3, 3, 2.0)
(2, 4, 11, 3, 7.0)

Arbitrary number of statistic functions given as a module

With this interface, any number of statistics can be requested, by wrapping them inside a module. For example: histogram_equiwidth[R, 10, STATS] where

• R is a relation
• 10 is the number of buckets
• STATS is a module that contains definitions of statistic functions.

For example:

@inline
module STATS
    def myAvg[F] = average[F]
    def mySum[F] = sum[F]
end

Because there is no order between the statistic functions of the module, this relation is ternary, with the middle argument specifying the name of the statistic function as a string: (bucket_id, stat_name, stat_value) where

• bucket_id is an integer identifier for the bucket starting from 1
• stat_name is a string that specifies the statistic function
• stat_value is the value of the statistic function applied on the bucket

Note that min, max, and count are included by default via this interface too, identified by the strings "min", "max", and "count" respectively.

Example 1

def T = {1; 2; 3; 4; 6; 11}
 
with histograms use histogram_equiwidth
 
@inline
module STATS
    def myAvg[F] = average[F]
    def mySum[F] = sum[F]
end
 
def output = histogram_equiwidth[T, 2, STATS]
(1, "myAvg", 2.5)
(2, "myAvg", 8.5)
(1, "max", 4)
(1, "min", 1)
(1, "count", 4)
(1, "mySum", 10)
(2, "max", 11)
(2, "min", 6)
(2, "count", 2)
(2, "mySum", 17)

Example 2

def T = {1; 2; 3; 4; 6; 11}
 
with histograms use histogram_equidepth
 
@inline
module STATS
    def myAvg[F] = average[F]
end
 
def output = histogram_equidepth[T, 2, STATS]
(1, "max", 3)
(1, "min", 1)
(1, "count", 3)
(2, "max", 11)
(2, "min", 4)
(2, "count", 3)
(1, "myAvg", 2.0)
(2, "myAvg", 7.0)