Tracking of multiple quantiles in dynamically varying data streams

Abstract

In this paper, we consider the problem of tracking multiple quantiles of dynamically varying data stream distributions. The method is based on making incremental updates of the quantile estimates every time a new sample is received. The method is memory and computationally efficient since it only stores one value for each quantile estimate and only performs one operation per quantile estimate when a new sample is received from the data stream. The estimates are realistic in the sense that the monotone property of quantiles is satisfied in every iteration. Experiments show that the method efficiently tracks multiple quantiles and outperforms state-of-the-art methods.

Appendix: Proof of Theorem 1

We will first present a theorem due to Norman [20] that will be used to prove Theorem 1. Norman [20] studied distance “diminishing models”. The convergence of ${\widehat{Q}}_n(q_k)$ to $Q(q_k)$ is a consequence of this theorem.

Theorem 2

Letx(t) be a stationary Markov process dependent on a constant parameter$\theta \in [0,1]$. Each$x(t) \in I$, whereIis a subset of the real line. Let$\delta x(t)=x(t+1)-x(t)$. The following are assumed to hold:

• 1. I is compact

• 2. $E [\delta x(t) | x(t)=y]= \theta w(y)+ O(\theta ^2)$

• 3. $Var [\delta x(t) | x(t)=y]= \theta ^2 s(y)+ O(\theta ^2)$

• 4. $E [\delta x(t)^3 | x(t)=y]= O(\theta ^3)$where$sup_{y \in I} \frac{O(\theta ^k)}{\theta ^k}< \infty$for$k=2,3$and$sup_{y \in I} \frac{o(\theta ^2)}{\theta ^2} \rightarrow 0$ as $\theta \rightarrow 0$

• 5. w(y) has a Lipschitz derivative inI

• 6. s(y) is LipschitzI.

If Assumptions 1 to 6 above hold,w(y) has a unique root$y^*$inIand$\frac{d w}{d y} \bigg |_{y=y^*} \le 0$then

• 1. $var [\delta x(t) | x(0)=x]=O(\theta )$uniformly for all$x \in I$and$t \ge 0$. For any$x \in I$, the differential equation$\frac{d y(\tau )}{d \tau }=w(y(t))$has a unique solution$y(\tau )=y(\tau ,x)$with$y(0)=x$and$E [\delta x(t) | x(0)=x]=y( t \theta )+O(\theta )$uniformly for all$x \in I$ and $t \ge 0$.

• 2. $\frac{x(t)-y(t \theta )}{\sqrt{\theta }}$has a normal distribution with zero mean and finite variance as$\theta \rightarrow 0$and$t \theta \rightarrow \infty$.

Having presented Theorem 2, we are now ready to prove Theorem 1 by resorting to Theorem 2. This is the main result of this paper. We will prove the convergence of ${\widehat{Q}}_n(q_k)$ for $k=2,3,\ldots ,K-1$ below. The proof for ${\widehat{Q}}_n(q_1)$ and ${\widehat{Q}}_n(q_K)$ can be done in the same manner and are not shown in this paper for the sake of brevity.

Proof

We now start by showing that the Markov process based on the updating rules (9)–(11) satisfies the assumptions 1 to 6 in Theorem 2.

$$\begin{aligned}&E\left( \delta {\widehat{Q}}_{n}(q_k)\,\left| \,{\widehat{Q}}_n(q_k)\right. \right)\\&\quad = E\left( \delta {\widehat{Q}}_{n}(q_k)\,\left| \,{\widehat{Q}}_n(q_k) \ge X\right. \right) P\left( {\widehat{Q}}_n(q_k) \ge X \right) \\&\qquad +E\left( \delta {\widehat{Q}}_{n}(q_k)\,|\,{\widehat{Q}}_n(q_k)< X\right) P\left( {\widehat{Q}}_n(q_k) < X\right) \\&\quad = \beta H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) q_k {\widehat{Q}}_{n}(q_{k})\left( 1 - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right)\\&\qquad - \beta H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) (1 - q_k) {\widehat{Q}}_{n}(q_{k}) F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \\&\quad = \beta H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) {\widehat{Q}}_{n}(q_{k}) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) \end{aligned}$$

(13)

We now let $\theta = \beta$, $y = {\widehat{Q}}_{n}(q_{k})$ and $w\left( {\widehat{Q}}_{n}(q_{k})\right)$ be equal to “everything” in (13) except $\beta$. It is easy to see that assumption 2 in Theorem 2 is satisfied. Next, we turn to assumption 5 which requires that $w\left( {\widehat{Q}}_{n}(q_{k})\right)$ has a Lipschitz derivative with respect to ${\widehat{Q}}_{n}(q_{k})$. Unfortunately it is not obvious that this is satisfied since H has a discontinuous derivative with respect to ${\widehat{Q}}_{n}(q_{k})$ due to the min-function in (6). To show that both assumptions 2 and 5 are satisfied, we need to perform a subtle modification of (13) as follows. A typical example of H as a function of ${\widehat{Q}}_{n}(q_{k})$ is shown as the black curve in Fig. 7. We define a function $H^{*}$ that is equal to H except for an the interval $[Q^{*} - \delta , Q^{*} + \delta ]$ (see Fig. 7). In the interval $[Q^{*} - \delta , Q^{*} + \delta ]$, $H^{*}$ is a function that is smaller then H (to satisfy the monotone property) and has a Lipschitz derivative. This requires that $H^{*}$ satisfy the following

$$\begin{aligned}&H^{*}\left( Q^{*} - \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&\quad =H\left( Q^{*} - \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&\frac{{\mathrm{d}} H^{*}}{{\mathrm{d}} {\widehat{Q}}_{n}(q_{k})} \left( Q^{*} - \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&\quad = \frac{{\mathrm{d}} H}{{\mathrm{d}} {\widehat{Q}}_{n}(q_{k})} \left( Q^{*} - \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&H^{*}\left( Q^{*} + \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&\quad = H\left( Q^{*} + \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&\frac{{\mathrm{d}} H^{*}}{{\mathrm{d}} {\widehat{Q}}_{n}(q_{k})} \left( Q^{*} + \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \\&\quad = \frac{{\mathrm{d}} H}{{\mathrm{d}} {\widehat{Q}}_{n}(q_{k})} \left( Q^{*} + \delta ; {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \end{aligned}$$

i.e. that the function value and the derivative must be equal for H and $H^{*}$ in $Q^{*} - \delta$ and $Q^{*} + \delta$. It is straightforward to satisfy these criteria, e.g. by fitting a polynomial. $H^{*}$ is illustrated as the grey curve in Fig. 7 (and is equal to H outside the interval). By reducing the value of $\delta$, $H^{*}$ will be more and more similar to H. In other words, there exists always a $\delta$ such that

$$\left| H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) - H^{*}\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) \right| < \beta \quad \forall \,{\widehat{Q}}_{n}(q_{k}) \in \left[ {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right]$$

which means that we can write

$$H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) = H^{*}\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) + O(\beta )$$

(14)

Substituting (14) into (13) we obtain

$$\beta H^{*} \left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) {\widehat{Q}}_{n}(q_{k}) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) + \beta {\widehat{Q}}_{n}(q_{k}) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) O(\beta ) = \beta H^{*} \left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) {\widehat{Q}}_{n}(q_{k}) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) + O(\beta ^2)$$

Since $H^{*}$ has a Lipschitz derivative, we see that with

$$w\left( {\widehat{Q}}_{n}(q_{k})\right) = H^{*}\left( {\widehat{Q}}_{n}(q_{k});{\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) {\widehat{Q}}_{n}(q_{k}) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right)$$

(15)

both assumptions 2 and 5 are satisfied.

Next we turn to assumption 3.

$$\begin{aligned}&E\left( \delta {\widehat{Q}}_{n}(q_k)^2\,\left| \,{\widehat{Q}}_n(q_k)\right. \right) \\&\quad = E\left( \delta {\widehat{Q}}_{n}(q_k)^2\,\left| \,{\widehat{Q}}_n(q_k) \ge X \right. \right) P\left( {\widehat{Q}}_n(q_k) \ge X \right) \\&\qquad + E\left( \delta {\widehat{Q}}_{n}(q_k)^2\,\left| \,{\widehat{Q}}_n(q_k)< X\right. \right) P\left( {\widehat{Q}}_n(q_k) < X\right) \\&\quad = \beta ^2 \left( H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) q_k {\widehat{Q}}_{n}(q_{k}) \right) ^2 \left( 1 - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) \\&\qquad - \beta ^2 \left( H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) (1 - q_k) {\widehat{Q}}_{n}(q_{k}) \right) ^2 F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \end{aligned}$$

$$\begin{aligned}&{\mathrm{Var}}\left( \delta {\widehat{Q}}_{n}(q_k)\,\left| \,{\widehat{Q}}_n(q_k)\right. \right) = E\left( \delta {\widehat{Q}}_{n}(q_k)^2\,\left| \,{\widehat{Q}}_n(q_k)\right. \right) - E\left( \delta {\widehat{Q}}_{n}(q_k)\,\left| \,{\widehat{Q}}_n(q_k)\right. \right) ^2\\ \nonumber&\quad = \beta ^2 \left( H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) q_k {\widehat{Q}}_{n}(q_{k}) \right) ^2 \left( 1 - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) \\ \nonumber&\qquad - \beta ^2 \left( H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) (1 - q_k) {\widehat{Q}}_{n}(q_{k}) \right) ^2 F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \\ \nonumber&\qquad + \beta ^2 \left( H\left( {\widehat{Q}}_{n}(q_{k}); {\widehat{Q}}_{n}(q_{k-1}), {\widehat{Q}}_{n}(q_{k+1}) \right) {\widehat{Q}}_{n}(q_{k}) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k})\right) \right) \right) ^2 \end{aligned}$$

(16)

We see that assumption 3 is satisfied with $s\left( {\widehat{Q}}_{n}(q_{k})\right)$ equal to everything in (16) except $\beta ^2$. Since H is Lipschitz (has a bounded derivative), $s\left( {\widehat{Q}}_{n}(q_{k})\right)$ is Lipschitz and assumption 6 is also satisfied. Assumption 4 can now be proved in the same manner.

We will use the results of Norman to prove the convergence. It is easy to see that $w\left( {\widehat{Q}}_{n}(q_{k})\right)$ in (15) admits two roots ${\widehat{Q}}_n(q_k) = {F_X}^{-1}(q_k) = Q(q_k)$ and ${\widehat{Q}}_n(q_k) = 0$. By introducing an arbitrarily small lower bound $Q_{\text {min}}>0$ on estimate ${\widehat{Q}}_{n}(q_{k})$, we can avoid the ${\widehat{Q}}_n(q_k)=0$. This is easily implemented by modifying the update rules and adding $Q_{\text {min}}$ to the right term of Eqs. (9)–(11). Therefore, the unique root becomes ${\widehat{Q}}_n(q_k)={F_X}^{-1}(q_k) = Q(q_k)$.

Fig. 7

The black and the grey curves show the functions H and $H^{*}$, respectively

We now differentiate to get

$$\frac{{\mathrm{d}}w\left( {\widehat{Q}}_{n}(q_{k})\right) }{{\mathrm{d}}{\widehat{Q}}_{n}(q_{k}) }= \left( \frac{{\mathrm{d}} H^{*}}{{\mathrm{d}} {\widehat{Q}}_{n}(q_{k})} + H^{*} \right) \left( q_k - F_X\left( {\widehat{Q}}_{n}(q_{k}) \right) - H^{*} {\widehat{Q}}_{n}(q_{k}) f\left( {\widehat{Q}}_{n}(q_{k})\right) \right)$$

We substitute the unique root $Q(q_k)$ for ${\widehat{Q}}_{n}(q_{k})$ and get

$$\begin{aligned}&\frac{ {\mathrm{d}}w\left( {\widehat{Q}}_{n}(q_{k})\right) }{{\mathrm{d}} {\widehat{Q}}_{n}(q_{k})} \bigg |_{{\widehat{Q}}_{n}(q_{k})=Q(q_k)}\\&\quad =\left( \frac{{\mathrm{d}} H^{*}}{{\mathrm{d}}{\widehat{Q}}_{n}(q_{k})} + H^{*} \right) (q_k - F_X\left( Q(q_{k}) \right) - H^{*} Q(q_{k}) f\left( Q(q_{k})\right) ) \\&\quad = 0-H^{*} Q(q_k) f_X(Q(q_k))<0. \end{aligned}$$

This gives

$$\lim _{n \beta \rightarrow \infty , \beta \rightarrow 0} E\left( {\widehat{Q}}_n(q_k)\right) =Q(q_k)+O(\beta )$$

and

$${\mathrm{Var}}\left( {\widehat{Q}}_n(q_k)\right) =O(\beta )$$

Consequently

$$\lim _{n \beta \rightarrow \infty , \beta \rightarrow 0} {\widehat{Q}}_n(q_k)=Q(q_k)$$

□