A Tight Lower Bound for Comparison-Based Quantile Summaries
A Tight Lower Bound for Comparison-Based Quantile Summaries
复制标题
基于比较的分位数摘要的严格下界
DOI：
10.1145/3375395.3387650
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
P. Veselý
中科院分区：
文献类型：
--
作者：
Graham Cormode;P. Veselý
分位数，如中位数或分位数，提供了关于从完全有序的宇宙中提取的项目集合的分布的简洁而有用的信息。我们研究数据结构，称为分位数摘要，它跟踪项目流的所有分位数，误差最多为ε。也就是说，ε-近似分位数摘要首先处理流，然后，给定任何分位数查询，从流中返回一个项，对于某些φ' = φ +- ε，该项是一个ε'-分位数。我们专注于基于比较的分位数摘要，它只能比较两个项目，否则就完全忽略了宇宙。迄今为止，由于Greenwald和卡纳[6]，最好的这种确定性分位数摘要最多存储O（1/ε log ε N）个项目，其中N是流中的项目数。我们证明，这个空间界是最佳的，显示匹配的下界。因此，我们的结果排除了在空间f（ε）<$o（log N）中构造基于确定性比较的分位数摘要的可能性，对于任何不依赖于N的函数f。作为推论，我们改进了有偏分位数的下限，这为（1+-ε）φ提供了更强的相对误差保证，并用于其他相关的计算任务。
Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a totally ordered universe. We study data structures, called quantile summaries, which keep track of all quantiles of a stream of items, up to an error of at most ε. That is, an ε-approximate quantile summary first processes a stream and then, given any quantile query 0łe φłe 1, returns an item from the stream, which is a φ'-quantile for some φ' = φ +- ε. We focus on comparison-based quantile summaries that can only compare two items and are otherwise completely oblivious of the universe. The best such deterministic quantile summary to date, due to Greenwald and Khanna [6], stores at most O(1/ε ⋅ log ε N) items, where N is the number of items in the stream. We prove that this space bound is optimal by showing a matching lower bound. Our result thus rules out the possibility of constructing a deterministic comparison-based quantile summary in space f(ε)⋅ o(log N), for any function f that does not depend on N. As a corollary, we improve the lower bound for biased quantiles, which provide a stronger, relative-error guarantee of (1+-ε)⋅ φ, and for other related computational tasks.