Method and apparatus for finding biased quantiles in data streams
OwnerGraham Cormode, Philip Korn +2inventors
InventorsGraham Cormode, Philip Korn, Shanmugavelayutham Muthukrishnan, Divesh Srivastava
Life of this patent
Estimating the term…
Abstract
A method and apparatus for computing biased or targeted quantiles are disclosed. For example, the present invention reads a plurality of items from a data stream and inserts each of the plurality of items that was read from the data stream into a data structure. Periodically, the data structure is compressed to reduce the number of stored items in the data structure. In turn, the compressed data structure can be used to output a biased or targeted quantile.
Claims20
A method for monitoring a data stream, comprising:
- reading a plurality of items from said data stream;
- inserting each of said plurality of items that was read from said data stream into a data structure;
- compressing said data structure periodically;
- and
- outputting at least one biased or targeted quantile from said data structure.
A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for monitoring a data stream, comprising:
- reading a plurality of items from said data stream;
- inserting each of said plurality of items that was read from said data stream into a data structure;
- compressing said data structure periodically;
- and
- outputting at least one biased or targeted quantile from said data structure.
An apparatus for monitoring a data stream, comprising:
- means for reading a plurality of items from said data stream;
- means for inserting each of said plurality of items that was read from said data stream into a data structure;
- means for compressing said data structure periodically;
- and
- means for outputting at least one biased or targeted quantile from said data structure.
Dependencies are inferred from the claim text.