Estimating Cardinality for Arbitrarily Large Data Stream With Improved Memory Efficiency

基数(数据建模) 计算机科学 估计员 数据流 约束(计算机辅助设计) 任务(项目管理) 算法 比例(比率) 并行计算 数据挖掘 数学 统计 物理 经济 电信 管理 量子力学 几何学
作者
Qingjun Xiao,Shigang Chen,You Zhou,Junzhou Luo
出处
期刊:IEEE ACM Transactions on Networking [Institute of Electrical and Electronics Engineers]
卷期号:28 (2): 433-446 被引量:27
标识
DOI:10.1109/tnet.2020.2970860
摘要

Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just one single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internet-scale database. To solve the problem, we propose an algorithm named HLL-TailCut, which implements the estimation standard error 1.0/√m using the memory units of four or three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 20%~45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
科研助手6应助华子黄采纳,获得10
刚刚
1秒前
快乐难敌发布了新的文献求助10
1秒前
1秒前
lyh416完成签到 ,获得积分10
2秒前
JamesPei应助羲和之梦采纳,获得10
5秒前
安静的冰蓝完成签到 ,获得积分10
6秒前
摩根完成签到,获得积分10
8秒前
科研通AI5应助零容忍采纳,获得10
9秒前
QQQ完成签到,获得积分20
9秒前
科研通AI5应助六出采纳,获得10
9秒前
11秒前
阳光c完成签到 ,获得积分10
12秒前
cdercder应助动人的凤凰采纳,获得10
12秒前
欧阳清水关注了科研通微信公众号
14秒前
田様应助guantlv采纳,获得10
15秒前
科研通AI5应助外向语蝶采纳,获得10
15秒前
大个应助闪闪翎采纳,获得10
15秒前
舒克完成签到,获得积分10
15秒前
16秒前
xxy完成签到,获得积分20
18秒前
18秒前
19秒前
20秒前
六出完成签到,获得积分10
21秒前
April完成签到 ,获得积分10
23秒前
山外山发布了新的文献求助30
24秒前
半夏完成签到,获得积分10
25秒前
葉鳳怡完成签到 ,获得积分10
25秒前
山川无恙发布了新的文献求助10
26秒前
冬瓜完成签到 ,获得积分10
28秒前
applelpypies完成签到 ,获得积分10
28秒前
酷炫翠桃完成签到,获得积分10
29秒前
30秒前
蓝调爱科研应助AnitaAdal采纳,获得10
30秒前
NN完成签到 ,获得积分10
31秒前
31秒前
31秒前
32秒前
沉静小萱发布了新的文献求助10
33秒前
高分求助中
Chinesen in Europa – Europäer in China: Journalisten, Spione, Studenten 500
Arthur Ewert: A Life for the Comintern 500
China's Relations With Japan 1945-83: The Role of Liao Chengzhi // Kurt Werner Radtke 500
Two Years in Peking 1965-1966: Book 1: Living and Teaching in Mao's China // Reginald Hunt 500
Epigenetic Drug Discovery 500
Hardness Tests and Hardness Number Conversions 300
Knowledge management in the fashion industry 300
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 物理 生物化学 纳米技术 计算机科学 化学工程 内科学 复合材料 物理化学 电极 遗传学 量子力学 基因 冶金 催化作用
热门帖子
关注 科研通微信公众号,转发送积分 3816929
求助须知:如何正确求助?哪些是违规求助? 3360303
关于积分的说明 10407548
捐赠科研通 3078290
什么是DOI,文献DOI怎么找? 1690694
邀请新用户注册赠送积分活动 813990
科研通“疑难数据库(出版商)”最低求助积分说明 767958