Sequential fixed-point quantile estimation

• US 20090138238A1
• Filed: 08/28/2008
• Published: 05/28/2009
• Est. Priority Date: 11/28/2007
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Bakshi, Yury, Hoeflin, David Arthur
• Granted Patent: US 8,000,929 B2
• Time in Patent Office: Days
• US Class Current: 702/180
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

Disclosed are method and apparatus for calculating a quantile estimate of a data stream. A quantile estimate is calculated iteratively by calculating a first quantile estimate and then calculating a second quantile estimate by adding a first update increment to the first estimate. A first observation sample is acquired. A first quantile estimate and a first standard deviation estimate are set to the sample quantile and the sample standard deviation of the first observation sample. A second observation sample is then acquired. A second standard deviation estimate is calculated based at least in part on the first standard deviation estimate and the sample standard deviation of the second observation sample. A first update increment is calculated based at least in part on the second observation sample and based at least in part on the product of the second standard deviation estimate times a log odds ratio function.

Claims

1. A method for calculating a quantile estimate of a data stream, comprising the steps of:

calculating a first quantile estimate based at least in part on a first sample quantile calculated from a first observation sample;

calculating a first standard deviation estimate based at least in part on a first sample standard deviation calculated from the first observation sample;

calculating a second sample standard deviation from a second observation sample;

calculating a second standard deviation estimate based at least in part on the first standard deviation estimate and the second sample standard deviation;

calculating a first update increment based at least in part on the second observation sample and based at least in part on the product of the second standard deviation estimate times a first value of a log odds ratio function; and

calculating a second quantile estimate as the sum of the first quantile estimate plus the first update increment.

2. The method of claim 1, further comprising the steps of:

calculating a third sample standard deviation estimate from a third observation sample;

calculating a third standard deviation estimate based at least in part on the second standard deviation estimate and the third sample standard deviation;

calculating a second update increment based at least in part on the third observation sample and based at least in part on the product of the third standard deviation estimate times a second value of the log odds ratio function; and

calculating a third quantile estimate as the sum of the second quantile estimate plus the second update increment.

3. The method of claim 2, wherein the step of calculating a third standard deviation estimate is performed according to:

{circumflex over (s)}₃=ω

×

{circumflex over (s)}₂+(1−

ω

)×

s₃,

where

ŝ

₃ is the third standard deviation estimate,

ω

is a weighting factor,

ŝ

₂ is the second standard deviation estimate, and

s₃ is the third sample standard deviation.

4. The method of claim 3, wherein the step of calculating a second update increment and the step of calculating a third quantile estimate is performed according to:

${\stackrel{⋒<br><br>}{T}}_3={\stackrel{⋒<br><br>}{T}}_2+{\stackrel{⋒<br><br>}{s}}_3\times <br><br>q\times <br><br>\ln \left(\frac{{\stackrel{⋒<br><br>}{q}}_i}{{\stackrel{⋒<br><br>}{p}}_i}\times <br><br>\frac{p}{q}\right)\times <br><br>\mathrm{gain}$ ${\stackrel{⋒<br><br>}{p}}_3=\left(M-n_{3,{\stackrel{⋒<br><br>}{T}}_2}+0.5\right)/\left(M+1\right)$ ${\stackrel{⋒<br><br>}{q}}_3=1-{\stackrel{⋒<br><br>}{p}}_3$

where

{circumflex over (T)}₃ is the third quantile estimate,

{circumflex over (T)}₂ is the second quantile estimate,

p designates the p^th quantile,

q=1−

p,

gain=a gain function,

{right arrow over (x)}₃=(x₃₁, x₃₂, . . . x_3j. . . x_3M) is the third observation sample where M is the number of observations in the third observation sample,

n_{3,{circumflex over (T)}2}=number of observations x_3j in the third observation sample such that x_3j>

{circumflex over (T)}₂, where {circumflex over (T)}₂ is a threshold value estimated during previous iteration.

5. The method of claim 4, wherein

the gain function is a first constant factor.

6. The method of claim 4, wherein

the gain function is multiplied by a smoothing function.

7. The method of claim 6, wherein

the smoothing function is a second constant factor.

8. The method of claim 4, wherein

the gain function is 1/√

{square root over (i)}.

9. The method of claim 1, wherein said data stream characterizes a traffic parameter in a communications network.

10. The method of claim 9, further comprising the step of:

re-directing traffic in response to the quantile estimate.

11. The method of claim 1, wherein said data stream characterizes a system variable in a system.

12. The method of claim 11, further comprising the step of:

adjusting a value of the system variable in response to the quantile estimate.

13. An apparatus for calculating a quantile estimate of a data stream, comprising:

means for calculating a first quantile estimate based at least in part on a first sample quantile calculated from a first observation sample;

means for calculating a first standard deviation estimate based at least in part on a first sample standard deviation calculated from the first observation sample;

means for calculating a second sample standard deviation from a second observation sample;

means for calculating a second standard deviation estimate based at least in part on the first standard deviation estimate and the second sample standard deviation;

means for calculating a first update increment based at least in part on the second observation sample and based at least in part on the product of the second standard deviation estimate times a first value of a log odds ratio function; and

means for calculating a second quantile estimate as the sum of the first quantile estimate plus the first update increment.

14. The apparatus of claim 13, further comprising:

means for calculating a third sample standard deviation estimate from a third observation sample;

means for calculating a third standard deviation estimate based at least in part on the second standard deviation estimate and the third sample standard deviation;

means for calculating a second update increment based at least in part on the third observation sample and based at least in part on the product of the third standard deviation estimate times a second value of the log odds ratio function; and

means for calculating a third quantile estimate as the sum of the second quantile estimate plus the second update increment.

15. The apparatus of claim 14, wherein the means for calculating a third standard deviation estimate further comprises means for calculating:

{circumflex over (s)}₃=ω

×

{circumflex over (s)}₂+(1−

ω

)×

s₃,

where

ŝ

₃ is the third standard deviation estimate,

ω

is a weighting factor,

ŝ

₂ is the second standard deviation estimate, and

s₃ is the third sample standard deviation.

16. The apparatus of claim 15, wherein the means for calculating a second update increment and the means for calculating a third quantile estimate further comprise means for calculating:

${\stackrel{⋒<br><br>}{T}}_3={\stackrel{⋒<br><br>}{T}}_2+{\stackrel{⋒<br><br>}{s}}_3\times <br><br>q\times <br><br>\ln \left(\frac{{\stackrel{⋒<br><br>}{q}}_i}{{\stackrel{⋒<br><br>}{p}}_i}\times <br><br>\frac{p}{q}\right)\times <br><br>\mathrm{gain}$ ${\stackrel{⋒<br><br>}{p}}_3=\left(M-n_{3,{\stackrel{⋒<br><br>}{T}}_2}+0.5\right)/\left(M+1\right)$ ${\stackrel{⋒<br><br>}{q}}_3=1-{\stackrel{⋒<br><br>}{p}}_3$

where

{circumflex over (T)}₃ is the third quantile estimate,

{circumflex over (T)}₂ is the second quantile estimate,

p designates the p^th quantile,

q=1−

p,

gain=a gain function,

{right arrow over (x)}₃=(x₃₁, x₃₂, . . . x_3j. . . , x_3M) is the third observation sample

where M is the number of observations in the third observation sample,

n_{3,{circumflex over (T)}2}=number of observations x_3j in the third observation sample such that x_3j>

{circumflex over (T)}₂, where {circumflex over (T)}₂ is a threshold value estimated during previous iteration.

17. The apparatus of claim 13, wherein said data stream characterizes a traffic parameter in a communications network.

18. The apparatus of claim 17, further comprising:

means for re-directing traffic in response to the quantile estimate.

19. The apparatus of claim 13, wherein said data stream characterizes a system variable in a system.

20. The apparatus of claim 19, further comprising:

means for adjusting a value of the system variable in response to the quantile estimate.

21. A computer readable medium storing computer program instructions for calculating a quantile estimate of a data stream, said computer instructions defining the steps of:

calculating a first quantile estimate based at least in part on a first sample quantile calculated from a first observation sample;

calculating a first standard deviation estimate based at least in part on a first sample standard deviation calculated from the first observation sample;

calculating a second sample standard deviation from the second observation sample;

calculating a second standard deviation estimate based at least in part on the first standard deviation estimate and the second sample standard deviation;

calculating a first update increment based at least in part on the second observation sample and based at least in part on the product of the second standard deviation estimate times a first value of a log odds ratio function; and

calculating a second quantile estimate as the sum of the first quantile estimate plus the first update increment.

22. The computer readable medium of claim 21, wherein the computer program instructions for calculating a quantile estimate of a data stream further comprise computer instructions defining the steps of:

calculating a third sample standard deviation estimate from a third observation sample;

calculating a third standard deviation estimate based at least in part on the second standard deviation estimate and the third sample standard deviation;

calculating a second update increment based at least in part on the third observation sample and based at least in part on the product of the third standard deviation estimate times a second value of the log odds ratio function; and

calculating a third quantile estimate as the sum of the second quantile estimate plus the second update increment.

23. The computer readable medium of claim 22, wherein the computer instructions defining the step of calculating a third standard deviation estimate further comprise computer instructions for calculating:

{circumflex over (s)}₃=ω

×

{circumflex over (s)}₂+(1−

ω

)×

s₃,

where

ŝ

₃ is the third standard deviation estimate,

ω

is a weighting factor,

ŝ

₂ is the second standard deviation estimate, and

s₃ is the third sample standard deviation.

24. The computer readable medium of claim 23, wherein the computer instructions defining the step of calculating a second update increment and the step of calculating a third quantile estimate further comprise computer instructions defining the steps of calculating:

${\stackrel{⋒<br><br>}{T}}_3={\stackrel{⋒<br><br>}{T}}_2+{\stackrel{⋒<br><br>}{s}}_3\times <br><br>q\times <br><br>\ln \left(\frac{{\stackrel{⋒<br><br>}{q}}_i}{{\stackrel{⋒<br><br>}{p}}_i}\times <br><br>\frac{p}{q}\right)\times <br><br>\mathrm{gain}$ ${\stackrel{⋒<br><br>}{p}}_3=\left(M-n_{3,{\stackrel{⋒<br><br>}{T}}_2}+0.5\right)/\left(M+1\right)$ ${\stackrel{⋒<br><br>}{q}}_3=1-{\stackrel{⋒<br><br>}{p}}_3$

where

{circumflex over (T)}₃ is the third quantile estimate,

{circumflex over (T)}₂ is the second quantile estimate,

p designates the p^th quantile,

q=1−

p,

gain=a gain function,

{right arrow over (x)}₃=(x₃₁, x₃₂, . . . x_3j. . . , x_3M) is the third observation sample

where M is the number of observations in the third observation sample,

n_{3,{circumflex over (T)}2}=number of observations x_3j in the third observation sample such that x_3j>

{circumflex over (T)}₂, where {circumflex over (T)}₂ is a threshold value estimated during previous iteration.

25. The computer readable medium of claim 21, wherein said data stream characterizes a traffic parameter in a communications network.

26. The computer readable medium of claim 25, wherein the computer instructions defining the steps of calculating a quantile estimate further comprise computer instructions for:

re-directing traffic in response to the quantile estimate.

27. The computer readable medium of claim 21, wherein said data stream characterizes a system variable in a system.

28. The method of claim 27, wherein the computer instructions defining the steps of calculating a quantile estimate further comprise computer instructions defining the step of:

adjusting a value of the system variable in response to the quantile estimate.