Methods and apparatus for computing estimated quantiles for streaming data over sliding windows
Estimated quantiles and/or percentiles for streaming data are computed over a sliding window. An exemplary method comprises obtaining a stream of data values; obtaining a summary of a distribution of previously processed data values; adding streamed data values to a buffer; and when the buffer reaches a predefined fullness threshold, performing the following steps: processing tuples in the summary to apply a decay function to each tuple using the number of items in the stream in the stream at the time the tuple is created and a minimal rank bound; for each item in the buffer, creating a tuple; adding the tuple to the summary, and removing the item from the buffer; and building a search tree that is used to process one or more of percentile queries and quantile queries. The summary is optionally compressed by merging consecutive tuples that satisfy a predefined invariant constraint. The decay function maintains, for example, one or more of a predefined recent number of items or a predefined recent time window of items in the summary.
1. A method, comprising the steps of:
obtaining a stream of data values;
obtaining a summary of a distribution of processed data values, wherein the processed data values correspond to data values of said stream that were previously: (i) streamed to a buffer and (ii) removed from the buffer, wherein said data values are stored in said summary as a tuple, wherein a given tuple, t i , comprises a given data value, an item count, a difference value based on a size of said summary at a time said tuple is created, a number of items in said stream at said time said tuple is created, and a minimal rank bound of tuple i−1;
adding streamed data values of said stream to said buffer; and
when the buffer reaches a predefined fullness threshold, performing the following steps:
processing tuples in the summary to apply a decay function to each tuple using said number of items in said stream and said minimal rank bound;
for each item in the buffer: (i) creating a tuple, (ii) adding the tuple to the summary, and (iii) removing the item from the buffer; and
building a search tree that is used to process one or more of percentile queries and quantile queries, wherein building said search tree comprises adding an entry to the search tree for each tuple in the summary.
2. The method of claim 1 , wherein, for each tuple in the summary, having a given data value, v i , the entry to the search tree is of the form (v i , percentile(v i )).
3. The method of claim 1 , wherein, for a given data value, v, a percentile of the given data value is the percentile(v i ) where v i is a largest value that is smaller than v.
4. The method of claim 1 , wherein, for a given percentile, a quantile is the value, v, at which the given percentile of the observations are less than v.
5. The method of claim 1 , wherein a result of said one or more of said percentile queries and said quantile queries is provided to one or more of a downstream system and an analyst to allow said given data value to be further analyzed.
6. The method of claim 1 , further comprising the step of compressing said summary by merging consecutive tuples that satisfy a predefined invariant constraint.
7. The method of claim 1 , wherein said decay function maintains one or more of a predefined recent number of items and items or a predefined recent time window of items in said summary.
8. The method of claim 1 , wherein said decay function comprises an exponential decay function based on a window size and a time since a last update of said summary.
9. The method of claim 1 , wherein said stream of data values comprises a stream of risk scores for a plurality of transactions.
10. A computer program product, comprising a non-transitory machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by at least one processing device perform the following steps: obtaining a stream of data values; obtaining a summary of a distribution of processed data values, wherein the processed data values correspond to data values of said stream that were previously: (i) streamed to a buffer and (ii) removed from the buffer, wherein said data values are stored in said summary as a tuple, wherein a given tuple, t comprises a given data value, an item count, a difference value based on a size of said summary at a time said tuple is created, a number of items in said stream at said time said tuple is created, and a minimal rank bound of tuple i−1; adding streamed data values of said steam to said buffer; and when the buffer reaches a predefined fullness threshold, performing the following steps: processing tuples in the summary to apply a decay function to each tuple using said number of items in said stream and said minimal rank bound; for each item in the buffer: (i) creating a tuple, (ii) adding the tuple to the summary, and (iii) removing the item from the buffer; and building a search tree that is used to process one or more of percentile queries and quantile queries, wherein building said search tree comprises adding an entry to the search tree for each tuple ii the summary.
11. The computer program product of claim 10 , wherein, for each tuple in the summary, having a given data value, v i , the entry to the search tree is of the form (v i , percentile (v i )).
12. The computer program product of claim 10 , wherein a result of said one or more of said percentile queries and said quantile queries is provided to one or more of a downstream system and an analyst to allow said given data value to be further analyzed.
13. The computer program product of claim 10 , further comprising the step of compressing said summary by merging consecutive tuples that satisfy a predefined invariant constraint.
14. The computer program product of claim 10 , wherein said decay function maintains one or more of a predefined recent number of items and a predefined recent time window of items in said summary.
15. The computer program product of claim 10 , wherein said decay function comprises an exponential decay function based on a window size and a time since a last update of said summary.
16. A system, comprising:
a memory; and
at least one processing device, coupled to the memory, operative to implement the following steps:
obtaining a stream of data values;
obtaining a summary of a distribution of processed data values, wherein the processed data values correspond to data values of said stream that were previously: (i) streamed to a buffer and (ii) removed from the buffer, wherein said data values are stored in said summary as a tuple, wherein a given tuple, t i , comprises a given data value, an item count, a difference value based on a size of said summary at a time said tuple is created, a number of items in said stream at said time said tuple is created, and a minimal rank bound of tuple i−1;
adding streamed data values of said stream to said buffer; and
when the buffer reaches a predefined fullness threshold, performing the following steps:
processing tuples in the summary to apply a decay function to each tuple using said number of items in said stream and said minimal rank bound;
for each item in the buffer: (i) creating a tuple, (ii) adding the tuple to the summary, and (iii) removing the item from the buffer; and
building a search tree that is used to process one or more of percentile queries and quantile queries, wherein building said search tree comprises adding an entry to the search tree for each tuple in the summary.
17. The system of claim 16 , wherein, for each tuple in the summary, having a given data value, v i , the entry to the search tree is of the form (v i , percentile(v i )).
18. The system of claim 16 , wherein a result of said one or more of said percentile queries and said quantile queries is provided to one or more of a downstream system and an analyst to allow said given data value to be further analyzed.
19. The system of claim 16 , further comprising the step of compressing said summary by merging consecutive tuples that satisfy a predefined invariant constraint.
20. The system of claim 16 , wherein said decay function maintains one or more of a predefined recent number of items or items and a predefined recent time window of items in said summary.
21. The system of claim 16 , wherein said decay function comprises an exponential decay function based on a window size and a time since a last update of said summary.
22. The system of claim 16 , wherein said stream of data values comprises a stream of risk scores for a plurality of transactions.