A General Method for Estimating Correlated Aggregates Over a Data Stream

摘要

On a stream of two dimensional data items where is an item identifier and is a numerical attribute, a correlated aggregate query asks to first apply a selection predicate along the dimension, followed by an aggregation along the dimension. For selection predicates of the form or , where parameter is provided at query time, we present new streaming algorithms and lower bounds for estimating correlated aggregates. Our main result is a general method that reduces the estimation of a correlated aggregate to the streaming computation of over an entire stream, for an aggregate that satisfies certain conditions. This results in the first sublinear space algorithms for the correlated estimation of a large family of statistics, including frequency moments. Our experimental validation shows that the memory requirements of these algorithms are significantly smaller than existing linear storage solutions, and that these achieve a fast per-record processing time. We also study the setting when items have weights. In the case when weights can be negative, we give a strong space lower bound which holds even if the algorithm is allowed up to a logarithmic number of passes over the data. We complement this with a small space algorithm which uses a logarithmic number of passes.