TCP - IP White Papers
Effective Computation of Biased Quantiles Over Data Streams
Overview Skew is prevalent in many data sources such as IP traffic streams. To continually summarize the distribution of such data, a high-biased set of quantiles (e.g., 50th, 90th and 99th percentiles) with finer error guarantees at higher ranks (e.g., errors of 5, 1 and 0.1 percent, respectively) is more useful than uniformly distributed quantiles (e.g., 25th, 50th and 75th percentiles) with uniform error guarantees. This paper addresses the following two problems. First, can a person compute quantiles with finer error guarantees for the higher ranks of the data distribution effectively, using less space and computation time than computing all quantiles uniformly at the finest error? Second, if specific quantiles and their error bounds are requested a priori, can the necessary space usage and computation time be reduced?.
| Publisher | Alcatel-Lucent | File Format | |
|---|---|---|---|
| Date Published | December 2006 | ||
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful?
White Paper RSS
Download
