Integer, Intent (In)	::	nb, nq, lrcomm, licomm
Integer, Intent (Inout)	::	ind, icomm(licomm), ifail
Integer, Intent (Out)	::	np
Real (Kind=nag_wp), Intent (In)	::	rv(), eps, q()
Real (Kind=nag_wp), Intent (Inout)	::	qv(*), rcomm(lrcomm)

C Header Interface

#include <nag.h>

void	g01apf_ (Integer ind, const double rv[], const Integer nb, const double eps, Integer np, const double q[], double qv[], const Integer nq, double rcomm[], const Integer lrcomm, Integer icomm[], const Integer licomm, Integer ifail)

The routine may be called by the names g01apf or nagf_stat_quantiles_stream_arbitrary.

3 Description

A quantile is a value which divides a frequency distribution such that there is a given proportion of data values below the quantile. For example, the median of a dataset is the

0.5

quantile because half the values are less than or equal to it.

g01apf uses a slightly modified version of an algorithm described in a paper by Zhang and Wang (2007) to determine

ε

-approximate quantiles of a large arbitrary-sized data stream of real values, where

ε

is a user-defined approximation factor. Let

m

denote the number of data elements processed so far then, given any quantile

q \in [0.0, 1.0]

, an

ε

-approximate quantile is defined as an element in the data stream whose rank falls within

[(q - ε) m, (q + ε) m]

. In case of more than one

ε

-approximate quantile being available, the one closest to

q m

is used.

4 References

Zhang Q and Wang W (2007) A fast algorithm for approximate quantiles in high speed data streams Proceedings of the 19th International Conference on Scientific and Statistical Database Management IEEE Computer Society 29

5 Arguments

1: $ind$ – Integer Input/Output

On initial entry: must be set to

0

On entry: indicates the action required in the current call to g01apf.

$ind = 0$: Initialize the communication arrays and attempt to process the first nb values from the data stream. eps, rv and nb must be set and licomm must be at least $10$ .
$ind = 1$: Attempt to process the next block of nb values from the data stream. The calling program must update rv and (if required) nb, and re-enter g01apf with all other parameters unchanged.
$ind = 2$: Continue calculation following the reallocation of either or both of the communication arrays rcomm and icomm.
$ind = 3$: Calculate the nq $ε$ -approximate quantiles specified in q. The calling program must set q and nq and re-enter g01apf with all other parameters unchanged. This option can be chosen only when $np \geq ⌈\exp (1.0) / eps⌉$ .

On exit: indicates output from the call.

$ind = 1$: g01apf has processed np data points and expects to be called again with additional data.
$ind = 2$: Either one or more of the communication arrays rcomm and icomm is too small. The new minimum lengths of rcomm and icomm have been returned in $icomm (1)$ and $icomm (2)$ respectively. If the new minimum length is greater than the current length then the corresponding communication array needs to be reallocated, its contents preserved and g01apf called again with all other parameters unchanged.
If there is more data to be processed, it is recommended that lrcomm and licomm are made significantly bigger than the minimum to limit the number of reallocations.
$ind = 3$: g01apf has returned the requested $ε$ -approximate quantiles in qv. These quantiles are based on np data points.

Constraint:

ind = 0

1

2

3

2: $rv (*)$ – Real (Kind=nag_wp) array Input

Note: the dimension of the array rv must be at least

nb

ind = 0

1

2

On entry: if

ind = 0

1

2

, the vector containing the current block of data, otherwise rv is not referenced.

3: $nb$ – Integer Input

On entry: if

ind = 0

1

2

, the size of the current block of data. The size of blocks of data in array rv can vary; therefore nb can change between calls to g01apf.

Constraint: if

ind = 0

1

2

nb > 0

4: $eps$ – Real (Kind=nag_wp) Input

On entry: approximation factor

ε

Constraint:

eps > 0.0 ​ and ​ eps \leq 1.0

5: $np$ – Integer Output

On exit:

m

, the number of elements processed so far.

6: $q (*)$ – Real (Kind=nag_wp) array Input

Note: the dimension of the array q must be at least

nq

ind = 3

On entry: if

ind = 3

, the quantiles to be calculated, otherwise q is not referenced. Note that

q (i) = 0.0

, corresponds to the minimum value and

q (i) = 1.0

to the maximum value.

Constraint: if

ind = 3

0.0 \leq q (i) \leq 1.0

, for

i = 1, 2, \dots, nq

7: $qv (*)$ – Real (Kind=nag_wp) array Output

Note: the dimension of the array qv must be at least

nq

ind = 3

On exit: if

ind = 3

qv (i)

contains the

ε

-approximate quantiles specified by the value provided in

q (i)

8: $nq$ – Integer Input

On entry: if

ind = 3

, the number of quantiles requested, otherwise nq is not referenced.

Constraint: if

ind = 3

nq > 0

9: $rcomm (lrcomm)$ – Real (Kind=nag_wp) array Communication Array

On entry: if

ind = 1

2

then the first

l

elements of rcomm as supplied to g01apf must be identical to the first

l

elements of rcomm returned from the last call to g01apf, where

l

is the value of lrcomm used in the last call. In other words, the contents of rcomm must not be altered between calls to this routine. If rcomm needs to be reallocated then its contents must be preserved. If

ind = 0

then rcomm need not be set.

On exit: rcomm holds information required by subsequent calls to g01apf.

10: $lrcomm$ – Integer Input

On entry: the dimension of the array rcomm as declared in the (sub)program from which g01apf is called.

Constraints:

if $ind = 0$ , $lrcomm \geq 1$ ;
otherwise $lrcomm \geq icomm (1)$ .

11: $icomm (licomm)$ – Integer array Communication Array

On entry: if

ind = 1

2

then the first

l

elements of icomm as supplied to g01apf must be identical to the first

l

elements of icomm returned from the last call to g01apf, where

l

is the value of licomm used in the last call. In other words, the contents of icomm must not be altered between calls to this routine. If icomm needs to be reallocated then its contents must be preserved. If

ind = 0

then icomm need not be set.

On exit:

icomm (1)

holds the minimum required length for rcomm and

icomm (2)

holds the minimum required length for icomm. The remaining elements of icomm are used for communication between subsequent calls to g01apf.

12: $licomm$ – Integer Input

On entry: the dimension of the array icomm as declared in the (sub)program from which g01apf is called.

Constraints:

if $ind = 0$ , $licomm \geq 10$ ;
otherwise $licomm \geq icomm (2)$ .

13: $ifail$ – Integer Input/Output

On entry: ifail must be set to

0

- 1

1

. If you are unfamiliar with this argument you should refer to Section 7 in the Introduction to the NAG Library CL Interface for details.

On exit:

ifail = 0

unless the routine detects an error (see Section 6).

As an out-of-core routine g01apf will only perform certain argument checks when a data checkpoint (including completion of data input) is signaled. As such it will usually be inappropriate to halt program execution when an error is detected since any errors may be subsequently resolved without losing any processing already carried out. Therefore setting ifail to a value of

- 1

1

is recommended. If the output of error messages is undesirable, the value

1

is recommended. When the value $- 1$ or $1$ is used it is essential to test the value of ifail on exit.

6 Error Indicators and Warnings

If on entry

ifail = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

$ifail = 1$: On entry, $ind = 〈value〉$ .
Constraint: $ind = 0$ , $1$ , $2$ or $3$ .

$ifail = 2$: On entry, $eps = 〈value〉$ .
Constraint: $0.0 < eps \leq 1.0$ .

$ifail = 3$: On entry, $ind = 0$ , $1$ or $2$ and $nb = 〈value〉$ .
Constraint: if $ind = 0$ , $1$ or $2$ then $nb > 0$ .

$ifail = 4$: On entry, $licomm = 〈value〉$ .
Constraint: $licomm \geq 10$ .

$ifail = 5$: On entry, $lrcomm = 〈value〉$ .
Constraint: $lrcomm \geq 1$ .

$ifail = 6$: The contents of icomm have been altered between calls to this routine.

$ifail = 7$: The contents of rcomm have been altered between calls to this routine.

$ifail = 8$: Number of data elements streamed, $〈value〉$ is not sufficient for a quantile query when $eps = 〈value〉$ .
Supply more data or reprocess the data with a higher eps value.

$ifail = 9$: On entry, $ind = 3$ and $nq = 〈value〉$ .
Constraint: if $ind = 3$ then $nq > 0$ .

$ifail = 10$: On entry, $ind = 3$ and $q (〈value〉) = 〈value〉$ .
Constraint: if $ind = 3$ then $0.0 \leq q (i) \leq 1.0$ for all $i$ .

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.

$ifail = - 999$: Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

Not applicable.

8 Parallelism and Performance

g01apf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.

Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

The average time taken by g01apf scales as

np \log (1 / ε \log (ε np))

It is not possible to determine in advance the final size of the communication arrays rcomm and icomm without knowing the size of the dataset. However, if a rough size (

n

) is known, the speed of the computation can be increased if the sizes of the communication arrays are not smaller than

\begin{array}{l} lrcomm & = & (\log_{2} (n \times eps + 1.0) - 2) \times ⌈1.0 / eps⌉ + 1 + x + 2 \times \min (x, ⌈x / 2.0⌉ + 1) \times y + 1 \\ licomm & = & (\log_{2} (n \times eps + 1.0) - 2) \times (2 \times (⌈1.0 / eps⌉ + 1) + 1) + \\ 2 \times (x + 2 \times \min (x, ⌈x / 2.0⌉ + 1) \times y) + y + 11 \end{array}

where

\begin{array}{l} x = \max (1, ⌊\log (eps \times n) / eps⌋) \\ y = \log_{2} (n / x + 1.0) + 1 . \end{array}

10 Example

This example computes a list of

ε

-approximate quantiles. The data is processed in blocks of

20

observations at a time to simulate a situation in which the data is made available in a piecemeal fashion.

g01ap: FL CL CPP AD

NAG FL Interfaceg01apf (quantiles_​stream_​arbitrary)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG FL Interface
g01apf (quantiles_stream_arbitrary)