Computer Science – Data Structures and Algorithms
Scientific paper
2006-12-05
Computer Science
Data Structures and Algorithms
11 pages
Scientific paper
The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}. 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 \cite{JKV07}. 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.
McGregor Andrew
Muthukrishnan Siddharth
No associations
LandOfFree
Estimating Aggregate Properties on Probabilistic Streams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Estimating Aggregate Properties on Probabilistic Streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating Aggregate Properties on Probabilistic Streams will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-452114