2006/12/05 by Andrew McGregor, S. Muthukrishnan, McGregor, Andrew +1
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #cs.DB #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0612031
11 pages
arxiv created 2006/12/05 · openalex publication_date 2006/12/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The probabilistic-stream model was introduced by Jayram et al. \citeJKV07. It is a generalization of the data stream model that is suited to handling ``probabilistic'' data where each item of the stream represents a probability distribution over a set of possible events. Therefore, a probabilistic stream determines a distribution over potentially a very large number of classical "deterministic" streams where each item is deterministically one of the domain values. The probabilistic model is applicable for not only analyzing streams where the input has uncertainties (such as sensor data streams that measure physical processes) but also where the streams are derived from the input data by post-processing, such as tagging or reconciling inconsistent and poor quality data. We present streaming algorithms for computing commonly used aggregates on a probabilistic stream. We present the first known, one pass streaming algorithm for estimating the \AVG, improving results in \citeJKV07. We present the first known streaming algorithms for estimating the number of \DISTINCT items on probabilistic streams. Further, we present extensions to other aggregates such as the repeat rate, quantiles, etc. In all cases, our algorithms work with provable accuracy guarantees and within the space constraints of the data stream model.