Randomized Error Removal for Online Spread Estimation in Data Streaming
Randomized Error Removal for Online Spread Estimation in Data Streaming
复制标题
DOI：
10.14778/3447689.3447707
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Haibo Wang;Chaoyi Ma;Olufemi O. Odegbile;Shigang Chen;J. Peir
中科院分区：
文献类型：
--
作者：
Haibo Wang;Chaoyi Ma;Olufemi O. Odegbile;Shigang Chen;J. Peir
实时测量来自大型、高速率数据流的流扩散有许多实际应用，其中数据流被建模为来自不同流的数据项的序列，而流的扩散是流中不同项的数量。在过去的几十年里，单流扩散估计的性能有了很大的提高。然而，在处理数据流中的大量流时，在减少内存占用的同时准确测量每个流的扩散仍然是一个巨大的挑战。本文的目的是引入新的多流扩频估计设计，其引起的处理开销和查询开销比现有技术要小得多，但在扩频估计方面实现了显著的精度提高。我们对这些新设计的性能进行了形式化分析。我们在硬件和软件上实现它们，并使用真实世界的数据跟踪来评估它们的性能，并与最先进的水平进行比较。实验结果表明，在估计精度、数据项处理吞吐量和在线查询吞吐量方面，我们最优的素描都比现有的最好的工作有了显著的提高。
Measuring flow spread in real time from large, high-rate data streams has numerous practical applications, where a data stream is modeled as a sequence of data items from different flows and the spread of a flow is the number of distinct items in the flow. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a data stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, data item processing throughput, and online query throughput.