Stream Sampling for Frequency Cap Statistics
Stream Sampling for Frequency Cap Statistics
复制标题
频次上限统计的流采样
DOI：
10.1145/2783258.2783279
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
E. Cohen
中科院分区：
文献类型：
--
作者：
E. Cohen
未聚合的数据以流或分布式的形式普遍存在，并且来自不同的来源，例如用户与Web服务和IP流量的交互。数据元素具有键(Cookie、用户、查询)和具有不同键的元素交错。对这种数据的分析通常利用被表示为对函数f的指定段中的键的总和的统计量，应用于键的频率(出现的总次数)。具体地说，DISTINCT是片段中活动键的数量，Sum是它们频率的总和，这两个都是频率上限统计的特殊情况，它通过参数T来限制频率。上限统计的一个重要应用是登台广告活动，其中上限参数是每个用户的最大印象数量的限制，我们估计合格印象的总数量。数据中不同的活动键的数量可能非常大，这使得精确计算查询的成本很高。相反，我们可以从样本中估计这些统计数据。给定函数f的最佳样本将包括频率为w的密钥，其概率大致与f(W)成正比。但是，尽管这样的“黄金标准”样本可以很容易地在聚合数据(键-频率对的集合)上计算，但准确的聚合本身成本高昂且速度慢。理想情况下，我们希望在没有聚合的情况下计算和维护样本。我们提出了一种非聚集数据的采样框架，它使用单遍(对于流)或两遍(对于分布式数据)，并且状态与期望的样本大小成比例。我们的设计统一了DISTINCT和SUM的经典解决方案。具体地说，我们的L封顶样本提供了任何单调非递减频率统计量的非负无偏估计，并且接近于T=Θ(L)的频率上限统计量的黄金标准估计。此外，我们的设计支持多目标样本，使用单个较小的样本为一组指定的统计数据提供严格的估计。
Unaggregated data, in a streamed or distributed form, is prevalent and comes from diverse sources such as interactions of users with web services and IP traffic. Data elements have keys (cookies, users, queries) and elements with different keys interleave. Analytics on such data typically utilizes statistics expressed as a sum over keys in a specified segment of a function f applied to the frequency (the total number of occurrences) of the key. In particular, Distinct is the number of active keys in the segment, Sum is the sum of their frequencies, and both are special cases of frequency cap statistics, which cap the frequency by a parameter T. One important application of cap statistics is staging advertisement campaigns, where the cap parameter is the limit of the maximum number of impressions per user and we estimate the total number of qualifying impressions. The number of distinct active keys in the data can be very large, making exact computation of queries costly. Instead, we can estimate these statistics from a sample. An optimal sample for a given function f would include a key with frequency w with probability roughly proportional to f(w). But while such a "gold-standard" sample can be easily computed over the aggregated data (the set of key-frequency pairs), exact aggregation itself is costly and slow. Ideally, we would like to compute and maintain a sample without aggregation. We present a sampling framework for unaggregated data that uses a single pass (for streams) or two passes (for distributed data) and state proportional to the desired sample size. Our design unifies classic solutions for Distinct and Sum. Specifically, our l-capped samples provide nonnegative unbiased estimates of any monotone non-decreasing frequency statistics, and close to gold-standard estimates for frequency cap statistics with T=Θ(l). Furthermore, our design facilitates multi-objective samples, which provide tight estimates for a specified set of statistics using a single smaller sample.