Compact Estimator for Streaming Triangle Counting

计算机科学 流式数据 数据挖掘
作者
Jiqing Gu,Chao Song,Haipeng Dai,Li Lu,Ming Liu
出处
期刊:IEEE Transactions on Knowledge and Data Engineering [IEEE Computer Society]
卷期号:36 (8): 3712-3724
标识
DOI:10.1109/tkde.2024.3371228
摘要

Streaming triangle counting is a critical issue in graph stream mining, with applications in dense subgraph discovery, web mining, anomaly detection, and more. Recent efforts have focused on estimating triangle counts in graph streams, primarily through sampling methods. However, because of limited memory resources for handling high speed streams, traditional sampling methods suffer from reduced sampling rate and thereby performance loss. In this paper, we propose a new compact data structure called uHLL to process edge streams by considering the tradeoff between estimation accuracy and memory efficiency. Furthermore, different from conventional triangle counting algorithms, we solve the estimation of union set cardinality for edge-local triangle count under both centralized and distributed framework, so as to efficiently estimate the global triangle count by a one-pass streaming algorithm. To the best of our knowledge, this is the first implementation of a distributed framework using a compact data structure for streaming triangle counting. We provide theoretical proof of unbiasedness and derive the variance of the union set and global triangle count. We compare our scheme with 11 algorithms, showing that under the same experimental setting, uHLL and distributed uHLL are at least 2.3 and 1.7 times more accurate than the state-of-the-art, respectively.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
dajiejie完成签到 ,获得积分10
刚刚
yi完成签到,获得积分10
6秒前
森林木完成签到,获得积分10
7秒前
明天更好完成签到 ,获得积分10
8秒前
燕子完成签到 ,获得积分10
9秒前
ilk666完成签到,获得积分10
10秒前
丘比特应助王子采纳,获得10
14秒前
g7001完成签到,获得积分10
14秒前
Leo_Sun完成签到,获得积分10
14秒前
满意的念柏完成签到,获得积分10
14秒前
上官若男应助Pt-SACs采纳,获得10
19秒前
合适的幻然完成签到,获得积分10
20秒前
厚朴大师完成签到,获得积分10
20秒前
淡然思卉完成签到,获得积分10
22秒前
22秒前
Asumita完成签到,获得积分10
24秒前
王子完成签到,获得积分10
24秒前
小薛完成签到,获得积分10
25秒前
王子发布了新的文献求助10
27秒前
keyaner完成签到,获得积分10
29秒前
29秒前
执着的导师完成签到,获得积分10
33秒前
倾听阳光完成签到 ,获得积分10
33秒前
琪琪完成签到,获得积分10
34秒前
盛宇大天才完成签到,获得积分10
36秒前
Wu完成签到 ,获得积分10
37秒前
秋秋完成签到 ,获得积分10
37秒前
Ava应助快乐的小乌龟采纳,获得10
38秒前
章鱼哥想毕业完成签到 ,获得积分10
40秒前
47秒前
bckl888完成签到,获得积分10
48秒前
48秒前
与离完成签到 ,获得积分10
49秒前
51秒前
小叶子完成签到 ,获得积分10
51秒前
偏翩完成签到 ,获得积分10
52秒前
KLED完成签到 ,获得积分10
55秒前
快乐的小乌龟完成签到,获得积分10
58秒前
啊哈啊哈额完成签到,获得积分10
59秒前
ZHZ完成签到,获得积分10
1分钟前
高分求助中
A new approach to the extrapolation of accelerated life test data 1000
Cognitive Neuroscience: The Biology of the Mind 1000
Technical Brochure TB 814: LPIT applications in HV gas insulated switchgear 1000
Immigrant Incorporation in East Asian Democracies 600
Nucleophilic substitution in azasydnone-modified dinitroanisoles 500
不知道标题是什么 500
A Preliminary Study on Correlation Between Independent Components of Facial Thermal Images and Subjective Assessment of Chronic Stress 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 3968578
求助须知:如何正确求助?哪些是违规求助? 3513391
关于积分的说明 11167428
捐赠科研通 3248822
什么是DOI,文献DOI怎么找? 1794499
邀请新用户注册赠送积分活动 875116
科研通“疑难数据库(出版商)”最低求助积分说明 804664