Panakos: Chasing the Tails for Multidimensional Data Streams
Panakos: Chasing the Tails for Multidimensional Data Streams
复制标题
DOI：
10.14778/3583140.3583147
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Fuheng Zhao;Punnal Ismail Khan;D. Agrawal;A. E. Abbadi;Arpit Gupta;Zaoxing Liu
中科院分区：
文献类型：
--
作者：
Fuheng Zhao;Punnal Ismail Khan;D. Agrawal;A. E. Abbadi;Arpit Gupta;Zaoxing Liu
系统操作员通常有兴趣从多维数据流中提取不同的特征流；并定期报告它们的分布，包括对特征分布尾部做出贡献的重要因素。用有限的资源满足这些提高数据速率的要求具有挑战性。本文介绍了 Panakos 的设计和实现，它充分利用可用资源来准确报告给定特征的分布、其尾部贡献者和其他流统计数据（例如基数、熵等）。我们的关键想法是利用现实世界中大多数特征流固有的偏度。我们通过根据特征值将特征流分解为热项、暖项和冷项来利用这种偏度。然后，我们使用不同的数据结构来跟踪每个类别中的对象。 Panakos提供了坚实的理论保证，并为各种任务实现了高性能。我们在软件和硬件上实现了 Panakos，并使用合成数据集和真实数据集将 Panakos 与其他最先进的草图进行了比较。实验结果表明，对于给定的内存预算，Panakos 的精度通常比最先进的解决方案高一个数量级。
System operators are often interested in extracting different feature streams from multi-dimensional data streams; and reporting their distributions at regular intervals, including the heavy hitters that contribute to the tail portion of the feature distribution. Satisfying these requirements to increase data rates with limited resources is challenging. This paper presents the design and implementation of Panakos that makes the best use of available resources to report a given feature's distribution accurately, its tail contributors, and other stream statistics (e.g., cardinality, entropy, etc.). Our key idea is to leverage the skewness inherent to most feature streams in the real world. We leverage this skewness by disentangling the feature stream into hot, warm, and cold items based on their feature values. We then use different data structures for tracking objects in each category. Panakos provides solid theoretical guarantees and achieves high performance for various tasks. We have implemented Panakos on both software and hardware and compared Panakos to other state-of-the-art sketches using synthetic and real-world datasets. The experimental results demonstrate that Panakos often achieves one order of magnitude better accuracy than the state-of-the-art solutions for a given memory budget.