We discuss the problem of counting distinct elements in a stream. A stream is usually considered as a sequence of elements that come one at a time. An exact solution to the problem requires memory space of the size of the stream. For many applications this solution is infeasible due to very large streams. The solution in that case, is to use a probabilistic data structure (also called sketch), from which we can estimate with high accuracy the cardinality of the stream. We present a new algorithm, ExtendedHyperLogLog (EHLL), which is based on the state-of-the-art algorithm, HyperLogLog (HLL). In order to achieve the same accuracy as HLL, EHLL uses 16% less memory. In recent years, a martingale approach has bean developed. In the martingale setting we receive better accuracy at the price of not being able to merge sketches. EHLL also works in the martingale setting. Martingale EHLL achieves the same accuracy as Martingale HLL using 12% less memory.


翻译:我们讨论在流中计算不同元素的问题。 流通常被视为一个元素序列, 一次产生一个元素。 问题的精确解决方案需要流体大小的记忆空间。 对于许多应用来说, 这个解决方案是无法做到的, 因为流体非常大。 在这种情况下, 解决办法是使用概率性数据结构( 也称为草图), 我们可以从中非常精确地估计流体的基点。 我们提出了一个新的算法, 扩展 HyperLogLog (ELL), 其基础是最新算法, 超LogLog (HLL) 。 为了实现与 HLL 相同的精确度, ELL 使用比 16 % 的记忆。 最近几年, martingale 方法已经形成。 在 martingale 设置中, 我们以无法合并草图的价格得到更好的精度。 ELL 还在 martingale 设置中工作 。 Martingale EHLLL 实现与 Martingale 低12% 的记忆一样的精度 。

0
下载
关闭预览

相关内容

机器学习系统设计系统评估标准
专知会员服务
78+阅读 · 2020年12月22日
专知会员服务
41+阅读 · 2020年12月18日
专知会员服务
52+阅读 · 2020年9月7日
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
333+阅读 · 2020年3月17日
机器学习速查手册,135页pdf
专知会员服务
337+阅读 · 2020年3月15日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
187+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
[情人节] jieba分词介绍
机器学习和数学
3+阅读 · 2018年2月14日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Arxiv
0+阅读 · 2021年8月10日
VIP会员
相关VIP内容
专知会员服务
78+阅读 · 2020年12月22日
专知会员服务
41+阅读 · 2020年12月18日
专知会员服务
52+阅读 · 2020年9月7日
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
333+阅读 · 2020年3月17日
机器学习速查手册,135页pdf
专知会员服务
337+阅读 · 2020年3月15日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
187+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
[情人节] jieba分词介绍
机器学习和数学
3+阅读 · 2018年2月14日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Top
微信扫码咨询专知VIP会员