Relative Error Streaming Quantiles
Relative Error Streaming Quantiles
复制标题
相对误差流分位数
DOI：
10.1145/3617891
复制
发表时间：
2023
影响因子：
2.5
通讯作者：
Veselý, Pavel
中科院分区：
文献类型：
--
作者：
Cormode, Graham;Karnin, Zohar;Liberty, Edo;Thaler, Justin;Veselý, Pavel
估计流数据的秩、分位数和分布是数据分析和监控的中心任务。给定一个来自数据宇宙的项流，该数据宇宙具有一个全序，任务是计算一个大小为多对数整数的草图（数据结构）。给定草图和查询项，应该能够近似其在流中的排名，即，流元素的数量小于或等于toy。迄今为止，大多数工作都集中在附加εnerror近似，最终在KLL草图中实现了最佳渐近行为。本文研究了秩的乘性（1± ε）-误差逼近.乘性误差的实际动机源于对了解分布尾部的需求，因此草图在极值附近更准确。由于先前的工作，最节省空间的算法存储O（log（ε2n）/ε2）或O（log 3（εn）/ε）论域项。我们提出了一个存储O（log1.5（εn）/ε）个项目的随机草图，它可以（1± ε）-近似每个论域项目的秩，具有高的恒定概率，这个空间界限在最优的一个因子之内。我们的算法不需要流长度的先验知识，是完全可合并的，使其适合于并行和分布式计算环境。
Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream ofnitems from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic inn. Given the sketch and a query itemy, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal toy.Most works to date focused on additive εnerror approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This article investigatesmultiplicative(1± ε)-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values.The most space-efficient algorithms due to prior work store either O(log (ε2n)/ε2) orO(log3(εn)/ε) universe items. We present a randomized sketch storingO(log1.5(εn)/ε) items that can (1± ε)-approximate the rank of each universe item with high constant probability; this space bound is within anfactor of optimal. Our algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments.
登录
查看更多内容
基于比较的分位数摘要的严格下界
DOI：
10.1145/3375395.3387650
发表时间：
2020
期刊：
Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
--
作者：
Graham Cormode;P. Veselý
通讯作者：
P. Veselý
DOI：
10.1145/3471485.3471488
发表时间：
2020-03
期刊：
ACM SIGMOD Record
影响因子：
--
作者：
Omri Ben-Eliezer;Rajesh Jayaram;David P. Woodruff;E. Yogev
通讯作者：
Omri Ben-Eliezer;Rajesh Jayaram;David P. Woodruff;E. Yogev
O((1/ε) log(1/ε)) 个字的随机在线分位数摘要
影响因子：
1
作者：
David Felber;R. Ostrovsky
通讯作者：
R. Ostrovsky
数据流中近似有偏分位数计算的有效算法
DOI：
10.1145/1321440.1321601
发表时间：
2007
期刊：
Sensors (Basel, Switzerland)
影响因子：
--
作者：
Qi Zhang;Wei Wang
通讯作者：
Wei Wang
理论与实践的中位数：相对误差分位数算法的最坏情况比较
DOI：
--
发表时间：
2021
期刊：
Knowledge Discovery and Data Mining
影响因子：
--
作者：
Graham Cormode;Abhinav Mishra;Joseph Ross;P. Vesel'y
通讯作者：
P. Vesel'y