Continuously Distinct Sampling over Centralized and Distributed High Speed Data Streams
Continuously Distinct Sampling over Centralized and Distributed High Speed Data Streams
复制标题
对集中式和分布式高速数据流进行连续不同采样
DOI：
10.1109/tpds.2018.2865452
复制
发表时间：
2019-02
影响因子：
5.3
通讯作者：
Guan Xiaohong
中科院分区：
文献类型：
--
作者：
Wang Pinghui;Wang Xiangyu;Tao Jing;Zhang Peng;Guan Xiaohong
不同采样是计算统计数据的基础（例如，访问特定网站的不同用户的年龄和性别分布），这取决于大型高速数据流（例如键更新对序列）中的不同键集（例如，用户id）。然而，现有方法的主要缺点是，它们需要确定数据流中的每个传入键当前是否在采样键集中，并跟踪采样键的更新聚合，从而产生较高的计算成本。为了解决这一挑战，我们开发了一种新方法</italic>随机投影和移除</italic> (RPE)，该方法使用bucket列表连续采样不同的键及其更新聚合。RPE处理每个键更新对的时间复杂度小且接近常数<inline-formula>< text -math notation="LaTeX">$O(1)$</ text -math><alternatives><inline-graphic xlink:href="wang-ieq1-2865452.gif"/></alternatives></inline-formula>。除了集中式数据流，我们还开发了一种新的DRPE方法来处理在多个分布式站点观察到的由密钥更新对组成的分布式数据流。我们在真实世界的数据集上进行了大量的实验，结果表明，RPE和DRPE将最先进方法的内存、计算和消息成本降低了几倍。
Distinct sampling is fundamental for computing statistics (e.g., the age and gender distribution of distinct users accessing a particular website) depending on the set of distinct keys (e.g., user IDs) in a large and high speed data stream such as a sequence of key-update pairs. However, the major shortcoming of existing methods is their high computational cost incurred by determining whether each incoming key in the data stream is currently in the set of sampled keys and keeping track of sampled keys’ update aggregations. To solve this challenge, we develop a new method <italic>random projection and eviction</italic> (RPE) that uses a list of buckets to continuously sample distinct keys and their update aggregations. RPE processes each key-update pair with small and nearly constant time complexity <inline-formula><tex-math notation="LaTeX">$O(1)$</tex-math><alternatives><inline-graphic xlink:href="wang-ieq1-2865452.gif"/></alternatives></inline-formula>. Besides centralized data streams, we also develop a novel method DRPE to deal with distributed data streams consisting of key-update pairs observed at multiple distributed sites. We conduct extensive experiments on real-world datasets, and the results demonstrate that RPE and DRPE reduce the memory, computational, and message costs of state-of-the-art methods by several times.
登录
查看更多内容
DOI：
10.2307/2346966
发表时间：
1977-11
期刊：
Applied statistics
影响因子：
--
作者：
A. Sunter
通讯作者：
A. Sunter
DOI：
10.1145/3084452
发表时间：
2017-04
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
You Zhou;Yian Zhou;Min Chen;Shigang Chen
通讯作者：
You Zhou;Yian Zhou;Min Chen;Shigang Chen
DOI：
--
发表时间：
2013-04
期刊：
--
影响因子：
--
作者：
Minlan Yu;Lavanya Jose;Rui Miao
通讯作者：
Minlan Yu;Lavanya Jose;Rui Miao
DOI：
10.1145/773153.773182
发表时间：
2003-06
期刊：
Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
Graham Cormode;S. Muthukrishnan
通讯作者：
Graham Cormode;S. Muthukrishnan
DOI：
10.1145/2487575.2487678
发表时间：
2012-12
期刊：
Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining
影响因子：
--
作者：
Madhav Jha;Seshadhri Comandur;Ali Pinar
通讯作者：
Madhav Jha;Seshadhri Comandur;Ali Pinar