New estimation algorithms for streaming data: Count-min can do more (extended version). http://www.cs.ualberta.ca/˜fandeng/ paper/cmm_full.pdf

Count-min is a general-purpose data stream summary technique, which can be used to answer multiple types of approximate queries such as multiplicity (a.k.a point) queries, join and self-join size estimations, and it has some nice properties such as the one-sided error guarantee, bet-ter space bounds and more accurate estimates for highly skewed data in comparison with the best known alterna-tives. However, based on our experiments for multiplicity queries and self-join size estimations on both synthetic and real data sets, we find that in practice the previous Count-min estimation algorithms only perform well when the data set is highly skewed; in other cases, these algorithms give much less accurate results than Fast-AGMS (a.k.a Count-sketch), which is an improvement based on the influential sketching technique, AMS sketch. In this paper, based on the existing Count-min data struc-ture, we propose two new estimation algorithms for multi-plicity queries and self-join size estimations, which signifi-cantly improve the estimation accuracies compared with the previous Count-min estimation algorithms when the data set is less skewed, exactly where the previous algorithms perform poorly. Moreover, we show both in theory and in practice that the performance of our algorithms are very similar to that of Fast-AGMS regardless of input data dis-tributions. Thus, with both the new and previous estimation algorithms, we argue that Count-min is more flexible and powerful than Fast-AGMS, because Count-min performs al-most the same as Fast-AGMS in terms of both estimation accuracy and time efficiency using our new estimation algo-rithms, while Count-min exhibits other nice properties using the previous estimation algorithms as mentioned before.