Can I read Approximate Quantiles and the Order of the Stream on EtoBox?

Approximate Quantiles and the Order of the Stream by Sudipto Guha; Andrew McGregor is a scholarly article available to read on EtoBox.

What is Approximate Quantiles and the Order of the Stream about?

Recently, there has been an increased focus on modeling uncertainty by distributions. Suppose we wish to compute a function of a stream whose elements are samples drawn independently from some distribution. The distribution is unknown, but the order in which the samples are presented to us will not be completely adversarial. In this paper, we investigate the importance of the ordering of a data stream, without making any assumptions about the actual distribution of the data. Using quantiles as an example application, we show that we can design provably better algorithms, and settle several open questions on the impact of order on streams. With the recent impetus in the investigation of models for sensor networks, we believe that our approach will allow the construction of novel and significantly improved algorithms.

Author

Sudipto Guha; Andrew McGregor

Publisher

ACM

Published

2006

Language

EN