BSR-TC: Adaptively Sampling for Accurate Triangle Counting over Evolving Graph Streams

doi:10.1142/S021819402140012X

	BSR-TC: Adaptively Sampling for Accurate Triangle Counting over Evolving Graph Streams
	Xuan, Wei; Cao, Huawei; Yan, Mingyu; Tang, Zhimin; Ye, Xiaochun; Fan, Dongrui
	2021-12-01
发表期刊	INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING
ISSN	0218-1940
卷号	31 期号:11N12 页码:1561-1581
摘要	Triangle counting is a fundamental graph mining problem, widely employed in various real-world application scenarios. Given the large scale of graph streams and limited memory space, it is feasible to achieve the estimation of global and local triangles by sampling. Existing streaming algorithms for triangle counting can be generalized into two categories: Reservoir-based methods and Bernoulli-based methods. The former use a fixed memory budget, whose size is difficult to set for accurate estimation without any prior knowledge about graph streams. The latter sample edges by a specified probability, but memory budget is uncontrollable for following a binomial distribution. In this work, we propose a novel and bounded-sampling-ratio algorithm for both global and local triangle counting, called BSR-TC, by adaptively resizing memory budget upwards over evolving graph streams. Specifically, our proposed single-pass BSR-TC can gain more advantage than the state-of-the-art algorithms over the continuous growth of graph streams. Experimental results show that BSR-TC achieves accuracy of at least 99.8% for global triangles, when the ratio of initial memory budget against whole graph streams >= 0.002% and given threshold = 20%, respectively.
关键词	Evolving graph streams triangle counting bounded sampling ratio
DOI	10.1142/S021819402140012X
收录类别	SCI
语种	英语
资助项目	National Natural Science of China[11904370] ; National Natural Science of China[61872335] ; National Natural Science of China[61732018] ; National Natural Science of China[61672499] ; State Key Laboratory of Computer Architecture[CARCH4509] ; State Key Laboratory of Mathematical Engineering[2019A07]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Computer Science, Software Engineering ; Engineering, Electrical & Electronic
WOS记录号	WOS:000746510600003
出版者	WORLD SCIENTIFIC PUBL CO PTE LTD
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/19011
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Cao, Huawei
作者单位	Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Xuan, Wei,Cao, Huawei,Yan, Mingyu,et al. BSR-TC: Adaptively Sampling for Accurate Triangle Counting over Evolving Graph Streams[J]. INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING,2021,31(11N12):1561-1581.
APA	Xuan, Wei,Cao, Huawei,Yan, Mingyu,Tang, Zhimin,Ye, Xiaochun,&Fan, Dongrui.(2021).BSR-TC: Adaptively Sampling for Accurate Triangle Counting over Evolving Graph Streams.INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING,31(11N12),1561-1581.
MLA	Xuan, Wei,et al."BSR-TC: Adaptively Sampling for Accurate Triangle Counting over Evolving Graph Streams".INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING 31.11N12(2021):1561-1581.