BSR-TC: Adaptively Sampling for Accurate Triangle Counting over Evolving Graph Streams
文献类型：期刊论文
| 作者 | Xuan, Wei; Cao, Huawei; Yan, Mingyu; Tang, Zhimin; Ye, Xiaochun; Fan, Dongrui |
| 刊名 | INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING
 |
| 出版日期 | 2021-12-01 |
| 卷号 | 31期号:11N12页码:1561-1581 |
| 关键词 | Evolving graph streams triangle counting bounded sampling ratio |
| ISSN号 | 0218-1940 |
| DOI | 10.1142/S021819402140012X |
| 英文摘要 | 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. |
| 资助项目 | 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记录号 | WOS:000746510600003 |
| 出版者 | WORLD SCIENTIFIC PUBL CO PTE LTD |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/19010]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。