class static
analytics.BiasedGk

Source: analyticsdoc.js:2683

The CKMS (GK adapted for biased quantiles) algorithm for online biased quantile estimation. Given a probability p the algorithm returns the approximate value of the p-th quantile. The algorithm is most accurate in one of the extremes (which extreme depends on the parameters).

The algorithm works by keeping a summary of buckets, each summarizing a range of values. Through the run of the algorithm new buckets are created and periodically merged if possible.

It was first explained in: "Effective Computation of Biased Quantiles over Data Streams" https:// www.cs.rutgers.edu/~muthu/bquant.pdf

Only the biased version is implemented (the targeted version is flawed).

The error is bounded by the rank of the element (not the absolute value). Specifically, the worst case relative error is bounded by max(epsp, epsp0) where eps is an accuracy paramter, p0 is the targetProb and p is the p-value set as the parameter of function quantile.

Properties

init
memory
samples
size

Methods

compress()
compress(val)
save(fout)
getParams()
quantile(pVals)

new BiasedGk([arg])

Example 

// import modules
var qm = require('qminer');
var fs = require('qminer').fs;
var quants = qm.analytics.quantiles;

// create the BiasedGk object
var gk = new quants.BiasedGk({
    eps: 0.1,
    targetProb: 0.99,
    compression: 'periodic',
    useBands: true
});

// create the data used for calculating quantiles
var inputs = [10, 1, 2, 8, 9, 5, 6, 4, 7, 3];

// fit the model
for (var i = 0; i < inputs.length; i++) {
    gk.insert(inputs[i]);
}

// make the estimation for the 0.1 quantile
var quant = gk.quantile(0.1);
// save the model
gk.save(fs.openWrite('gk.bin')).close();
// open the gk model under a new variable
var gk2 = new analytics.quantiles.BiasedGk(fs.openRead('gk.bin'));

Parameter

Name Type Optional Description

arg

(module:analytics.quantiles~BiasedGkParam or module:fs:FIn)

Yes

Constructor arguments. There are 2 ways of constructing:
1. Using the module:analytics.quantiles~BiasedGkParam object,
2. using the file input stream module:fs.FIn.

Properties

static
init

Indicates whether the model is initialized (has seen at least one value).

static
memory

Returns the models current memory consumption.

static
samples

Returns the number of samples seen by the model.

static
size

Returns the current size of the algorithms summary in number of tuples.

Methods

static
compress()

Manually runs the compression procedure.

Returns

reference to self

static
compress(val) → module:analytics.quantiles.Gk

Adds a new value to the summary.

Example 

var qm = require('qminer');

var gk = new qm.analytics.quantiles.BiasedGk();
gk.insert(1.0);
gk.insert(2.0);

Parameter

Name Type Optional Description

val

number

 

the value
Returns

module:analytics.quantiles.Gk reference to self

static
save(fout) → module:fs.FOut

Saves the objects state into the output stream.

Parameter

Name Type Optional Description

fout

module:fs.FOut

 

the output stream
Returns

module:fs.FOut - the output stream

getParams() → module:analytics.quantiles~BiasedGkParam

Returns the models' parameters as a JavaScript object (JSON). These parameters are the same as are set through the constructor.

Returns

module:analytics.quantiles~BiasedGkParam The construction parameters.

var analytics = qm.analytics; var gk = new analytics.quantiles.BiasedGk(); var params = gk.getParams();

console.log(params.targetProb); console.log(params.eps); console.log(params.autoCompress); console.log(params.useBands);

quantile(pVals) → (number or Array)

Given an input cumulative probability, returns a quantile associated with that probability (e.g. for input 0.5 it will return the median).

Example 

var qm = require('qminer');

var gk = new qm.analytics.quantiles.BiasedGk({
    eps: 0.1,
    targetProb: 0.01
});
gk.insert(1.0);
gk.insert(2.0);
gk.insert(1.0);
gk.insert(3.0);
gk.insert(2.0);

console.log(gk.quantile(0.01));   // prints the first percentile
console.log(gk.quantile(0.25));   // prints the first quartile
console.log(gk.quantile(0.5));    // prints the median

Parameter

Name Type Optional Description

pVals

(number or Array)

 

the p-values which we a querying
Returns

(number or Array) quantiles - depending whether the input was a single value or array the method returns a quantile or array of quantiles