Range-Efficient Counting of Distinct Elements in a Massive Data Stream
Range-Efficient Counting of Distinct Elements in a Massive Data Stream
复制标题
海量数据流中不同元素的范围有效计数
DOI：
10.1137/050643672
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Srikanta Tirthapura
中科院分区：
文献类型：
--
作者：
A. Pavan;Srikanta Tirthapura
对$F_0$（数据流中不同元素的数量）的一次有效估计是数据库和网络中各种上下文中出现的一个基本问题。我们考虑$F_0$的范围有效估计：估计数据流中不同元素的数量，其中流的每个元素不仅仅是一个整数，而是一个整数区间。我们提出了一种随机算法，它产生$F_0$的（e, d）近似，具有以下时间和空间复杂性（$n$是项目的范围的大小）：(1)每个间隔的平摊处理时间为$O(\log{\frac{1}{\delta}}\log \frac{n}{\epsilon})$。(2)使用的工作空间为$O(\frac{1}{\epsilon^2}\log{\frac{1}{\delta}}\log n)$ bits。我们的算法改进了Bar-Yossef， Kumar和Sivakumar先前的算法[$13$ ACM-SIAM离散算法研讨会论文集（SODA）， 2002, pp. 623-632]，该算法需要$O(\frac{1}{\epsilon^5} \log{\frac{1}{\delta}}\log^5 n)$每个项目的处理时间。该算法也可用于计算多信号流的最大优势范数，并显著改进了Cormode和Muthukrishnan先前的最佳时间和空间界限[$11$欧洲算法研讨会（ESA）论文集，Lecture Notes in computing]。科学通报，2003,(1),pp. 148-160。该算法还为传感器网络中数据聚合过程中出现的不同求和问题提供了有效的解决方案[$2$和嵌入式网络传感器系统国际会议论文集，ACM出版社，纽约，2004年，第250-262页，$20$第六届数据工程国际会议论文集（ICDE）， 2004年，第449-460页]。
Efficient one-pass estimation of $F_0$, the number of distinct elements in a data stream, is a fundamental problem arising in various contexts in databases and networking. We consider range-efficient estimation of $F_0$: estimation of the number of distinct elements in a data stream where each element of the stream is not just a single integer but an interval of integers. We present a randomized algorithm which yields an (e, d)-approximation of $F_0$, with the following time and space complexities ($n$ is the size of the universe of the items): (1) The amortized processing time per interval is $O(\log{\frac{1}{\delta}}\log \frac{n}{\epsilon})$. (2) The workspace used is $O(\frac{1}{\epsilon^2}\log{\frac{1}{\delta}}\log n)$ bits. Our algorithm improves upon a previous algorithm by Bar-Yossef, Kumar and Sivakumar [Proceedings of the $13$th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, pp. 623-632], which requires $O(\frac{1}{\epsilon^5} \log{\frac{1}{\delta}}\log^5 n)$ processing time per item. This algorithm can also be used to compute the max-dominance norm of a stream of multiple signals and significantly improves upon the previous best time and space bounds by Cormode and Muthukrishnan [Proceedings of the $11$th European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 2938, Springer, Berlin, 2003, pp. 148-160]. This algorithm also provides an efficient solution to the distinct summation problem, which arises during data aggregation in sensor networks [Proceedings of the $2$nd International Conference on Embedded Networked Sensor Systems, ACM Press, New York, 2004, pp. 250-262, Proceedings of the $20$th International Conference on Data Engineering (ICDE), 2004, pp. 449-460].