Method and apparatus for incremental tracking of multiple quantiles
View Patent ↗A capability for incremental tracking of multiples quantiles is provided. A method for performing an incremental quantile update using a data value of a received data record includes determining an initial distribution function, updating the initial distribution function to form a new distribution function based on the received data value, generating an approximation of the new distribution function, and determining new quantile estimates from the approximation of the new distribution function. The initial distribution function includes a plurality of initial quantile estimates and a respective plurality of initial probabilities. The new distribution function includes a plurality of quantile points identifying the respective initial quantile estimates and a respective plurality of new probabilities associated with the initial quantile estimates. The approximation of the new distribution function is generated by connecting pairs of adjacent quantile points using linear approximations of regions between the pairs of adjacent quantile points.
1. A method, comprising:
generating, using a processor, an approximation of a quantile distribution function by connecting a pair of adjacent quantile points using linear interpolation;
wherein the pair of adjacent quantile points comprises:
a first quantile point having a first quantile estimate and a first probability associated therewith; and
a second quantile point having a second quantile estimate and a second probability associated therewith; and
wherein generating the approximation of the quantile distribution function comprises:
defining a right quantile point to the right of the first quantile point in the quantile distribution function;
defining a left quantile point to the left of the second quantile point in the quantile distribution function; and
connecting the first quantile point, the right quantile point, the left quantile point, and the second quantile point using linear interpolation.
2. The method of claim 1 , wherein the right quantile point is defined using right t (i)=(S t−1 (i)+Δ t (i), p t (i)+f t−1 (i)Δ t (i)), wherein:
S t−1 (i) is the first quantile estimate associated with the first quantile point;
p t (i) is the first probability associated with the first quantile estimate of the first quantile point;
f t−1 (i) is a density estimate associated with the first quantile estimate of the first quantile point; and
Δ t (i) is a monotonicity value.
3. The method of claim 1 , wherein the left quantile point is defined using left t (i+1)=(S t−1 (i+1)−Δ t (i), p t (i+1)−f t−1 (i+1)Δ t (i)), wherein:
S t−1 (i+1) is the second quantile estimate associated with the second quantile point;
p t (i+1) is the second probability associated with the second quantile estimate of the second quantile point;
f t−1 (i+1) is a density estimate associated with the second quantile estimate of the second quantile point; and
Δ t (i) is a monotonicity value.
4. The method of claim 1 , wherein the first quantile point and the right quantile point are connected linearly, the right quantile point and the left quantile point are connected linearly, and the left quantile point and the second quantile point are connected linearly.
5. The method of claim 1 , wherein generating the approximation of the quantile distribution function comprises:
computing a monotonicity value Δ t (i) using:
Δ
t
(
i
)
=
min
(
S
t
-
1
(
i
+
1
)
-
S
t
-
1
(
i
)
2
,
p
t
(
i
+
1
)
-
p
t
(
i
)
)
f
t
-
1
(
i
)
+
f
t
-
1
(
i
+
1
)
)
,
wherein:
S t−1 (i) is the first quantile estimate associated with the first quantile point;
p t (i) is the first probability associated with the first quantile estimate of the first quantile point;
f t−1 (i) is a first density estimate associated with the first quantile estimate of the first quantile point;
S t−1 (i+1) is the second quantile estimate associated with the second quantile point;
p t (i+1) is the second probability associated with the second quantile estimate of the second quantile point; and
f t−1 (i+1) is a second density estimate associated with the second quantile estimate of the second quantile point.
6. The method of claim 1 , further comprising:
prior to generating the approximation of the quantile distribution function:
generating the quantile distribution function by updating an initial quantile distribution function based on a received data value.
7. The method of claim 6 , wherein the initial quantile distribution function comprises a first initial quantile estimate having a first initial probability associated therewith, wherein updating the initial quantile distribution function comprises:
determining a second initial probability associated with the first initial quantile estimate.
8. The method of claim 7 , wherein determining the second initial probability associated with the first initial quantile estimate comprises:
evaluating p t (i)=(1−w t ) p t−1 (i)+w t I(S t−1 (i)≧x t ) for the first initial quantile estimate, wherein:
x t is the received data value;
w t is a weight associated with the received data value;
S t−1 (i) is the first initial quantile estimate;
p t−1 (i) is the first initial probability associated with the first initial quantile estimate;
I(S t−1 (i)≧x t ) is an indicator function; and
p t (i) is the second initial probability associated with the first initial quantile estimate.
9. The method of claim 1 , further comprising:
determining an updated first quantile estimate associated with the first probability based on the approximation of the quantile distribution function.
10. The method of claim 9 , wherein determining the updated first quantile estimate associated with the first probability based on the approximation of the quantile distribution function comprises:
evaluating the approximation of the quantile distribution function using the first probability as an input.
11. The method of claim 9 , wherein determining the updated first quantile estimate associated with the first probability based on the approximation of the quantile distribution function comprises:
evaluating {circumflex over (F)} t (S t (i))=p i , wherein
{circumflex over (F)} t is the approximation of the quantile distribution function;
S t (i) is the updated first quantile estimate; and
p i is the first probability.
12. The method of claim 1 , wherein the quantile distribution function has a first density estimate associated therewith, wherein the first density estimate is associated with the first quantile point, wherein the method further comprises:
updating the first density estimate of the quantile distribution function to form a second density estimate using f t (i)=(1−w t )f t−1 (i)+w t I(|x t −S t (i)|≦c /{2c}), wherein:
x t is a received data value;
w t is a weight associated with the received data value;
S t (i) is the first quantile estimate associated with the first quantile point;
f t−1 (i) is the first density estimate associated with the first quantile point;
I(|x t −S t−1 (i)≦c) is an indicator function;
c is a tunable parameter representing a window size; and
f t (i) is the second density estimate.
13. The method of claim 1 , further comprising:
prior to generating the approximation of the quantile distribution function:
generating the quantile distribution function by updating an initial quantile distribution function based on a received data value, wherein the initial quantile distribution function comprises a first initial quantile estimate having a first initial probability associated therewith, wherein updating the initial quantile distribution function comprises determining a second initial probability associated with the first initial quantile estimate.
14. A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:
generating an approximation of a quantile distribution function by connecting a pair of adjacent quantile points using linear interpolation;
wherein the pair of adjacent quantile points comprises:
a first quantile point having a first quantile estimate and a first probability associated therewith; and
a second quantile point having a second quantile estimate and a second probability associated therewith; and
wherein generating the approximation of the quantile distribution function comprises:
defining a right quantile point to the right of the first quantile point in the quantile distribution function;
defining a left quantile point to the left of the second quantile point in the quantile distribution function; and
connecting the first quantile point, the right quantile point, the left quantile point, and the second quantile point using linear interpolation.
15. An apparatus, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
generate an approximation of a quantile distribution function by connecting a pair of adjacent quantile points using linear interpolation;
wherein the pair of adjacent quantile points comprises:
a first quantile point having a first quantile estimate and a first probability associated therewith; and
a second quantile point having a second quantile estimate and a second probability associated therewith; and
wherein the processor is configured to generate the approximation of the quantile distribution function by:
defining a right quantile point to the right of the first quantile point in the quantile distribution function;
defining a left quantile point to the left of the second quantile point in the quantile distribution function; and
connecting the first quantile point, the right quantile point, the left quantile point, and the second quantile point using linear interpolation.