Article(id=1325495561905910697, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1325495515563041259, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202550151, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1740758400000, receivedDateStr=2025-03-01, revisedDate=1757260800000, revisedDateStr=2025-09-08, acceptedDate=1760112000000, acceptedDateStr=2025-10-11, onlineDate=1793952368475, onlineDateStr=2026-11-06, pubDate=1772294400000, pubDateStr=2026-03-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1793952368475, onlineIssueDateStr=2026-11-06, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1793952368475, creator=13701087609, updateTime=1793952368475, updator=13701087609, issue=Issue{id=1325495515563041259, tenantId=1146029695717560320, journalId=1324759914146529478, year='2026', volume='63', issue='3', pageStart='539', pageEnd='823', issueExtLink='null', onlineDate='null', pubDate='1772294400000', pubDateStr='2026-03-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1793952357425, creator='13701087609', updateTime=1793952549954, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1325496323193057998, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1325495515563041259, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1325496323193057999, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1325495515563041259, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=798, endPage=811, ext={EN=ArticleExt(id=1325495562128208810, articleId=1325495561905910697, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Parallel Streaming Graph Processing with Hybrid Incremental Computation, columnId=1325493593498059289, journalTitle=Journal of Computer Research and Development, columnName=High Performance Computing, runingTitle=null, highlight=null, articleAbstract=

Streaming graphs can effectively model rapidly changing data in real life, and have been widely used in social network analysis, content recommendation, anomaly detection, and other fields. Based on the fact that the two graph snapshots before and after the graph update have a large amount of the same data, incremental computation reduces the amount of memory accesses and computation in the iterations by storing and reusing the historical results, which effectively improves the performance of streaming graph processing. However, the existing solutions for incremental computation optimization of graph algorithms are often limited by graph algorithms that satisfy specific properties, thus it is difficult to apply them to general graph algorithms. In this paper, the incremental computation is further divided into two modes of refinement and recomputation. The similarities and differences between the two modes are analyzed theoretically, and the performance differences between them are tested experimentally with different datasets, algorithms, and update settings. Based on the two modes, the hybrid incremental computation mode is designed to ensure the correctness of switching, and the switching time is predicted accurately by random forest classifiers. Through performance evaluation and switching effect analysis, it is proved that the general graph algorithms can effectively switch under the hybrid mode. Compared with the state-of-the-art solution DZIG, the average speedup is 1.25.

, authors=Yue Shen1, 2, 3, Jie Zhang1, Yuan Zhang1, *, Huawei Cao1, 2, 3, Xuejun An1, 2, 3, Xiaochun Ye1, authorsList=Yue Shen, Jie Zhang, Yuan Zhang, Huawei Cao, Xuejun An, Xiaochun Ye, authorCompany=null, correspAuthors=Yuan Zhang, authorNote=

born in 1999. PhD candidate. Member of CCF. Her main research interests include parallel computing and dynamic graph processing

born in 1999. Master, assistant engineer. Her main research interests include high-performance computing and graph algorithm optimization

born in 1990. PhD, engineer. Member of CCF. Her main research interests include high-performance computing and graph algorithm optimization

born in 1989. PhD, associate professor, master supervisor. Member of CCF. His main research interests include parallel computing and high throughput computing architecture

born in 1966. PhD, senior engineer, PhD supervisor. Member of CCF. His main research interests include computer system architecture and high-performance interconnection networks

born in 1981. PhD, professor, PhD supervisor. Member of CCF. His main research interests include algorithm paralleling and optimizing software simulation, and architecture for high throughput computer

, correspAuthorsNote=null, copyrightStatement=Copyright © 2026 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1325495566976824261, articleId=1325495561905910697, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=基于混合增量计算的流式图并行处理, columnId=1325493595259666971, journalTitle=计算机研究与发展, columnName=高性能计算, runingTitle=null, highlight=null, articleAbstract=

流式图能够对现实生活中数据快速变化的场景进行有效建模,在社交网络分析、内容推荐、异常检测等领域得到了广泛应用。基于流式图更新前后的2个图快照具有大量相同数据的事实,增量计算通过对历史计算结果进行存储和复用来降低迭代计算过程中的访存量和计算量,从而有效提升流式图处理的性能。然而,现有对图算法进行增量计算优化的研究往往受限于满足特定性质的图算法,而难以应用于通用图算法。针对通用图算法的增量计算优化问题,将增量计算进一步划分为基于修正和基于重计算的增量计算模式。理论上刨析了二者的异同点,实验上在不同图数据集、图算法和更新场景设置下测试了二者的性能差异。提出了混合增量计算模式,设计了确保切换正确性的算法,并通过随机森林分类器准确地预测切换时机。性能评估和切换效果分析表明通用图算法在混合增量计算模式下能够进行有效切换,并相比先进的流式图处理系统DZIG实现了平均1.25的加速比。

, authors=申玥1, 2, 3, 张婕1, 张园1, *, 曹华伟1, 2, 3, 安学军1, 2, 3, 叶笑春1, authorsList=申玥, 张婕, 张园, 曹华伟, 安学军, 叶笑春, authorCompany=null, correspAuthors=张园, authorNote=

1999年生。博士研究生。CCF会员。主要研究方向为并行计算、动态图处理

1999年生。硕士,助理工程师。主要研究方向为高性能计算、图算法优化

1990年生。博士,工程师。CCF 会员。主要研究方向为高性能计算、图算法优化

1989年生。博士,副研究员,硕士生导师。CCF会员。主要研究方向为并行计算、高通量计算架构

1966年生。博士,高级工程师,博士生导师。CCF会员。主要研究方向为计算机系统结构、高性能互连网络

1981年生。博士,研究员,博士生导师。CCF会员。主要研究方向为算法并行与优化软件仿真、高通量计算机体系结构

, correspAuthorsNote=
张园()
, copyrightStatement=版权所有 © 2026 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=410Drl1pJLa8258u1Vof9w==, magXml=+S0Hlj5uspSjQ0B7+Tn9/w==, pdfUrl=null, pdf=8vsDlHaxyzEkg1IM5c/ONg==, pdfFileSize=2615361, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=TQx8NAWo4MId+3w39U/j8A==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=JRLUm5DEwpIX78/MExvOIQ==, mapNumber=null, fund=null)}, authors=[Author(id=1325495569254331344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=shenyue24b@ict.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495569388549076, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569254331344, language=EN, stringName=Yue Shen, firstName=Yue, middleName=null, lastName=Shen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
2University of Chinese Academy of Sciences, Beijing 100049
3Zhongguancun Laboratory, Beijing 100094, bio={"content":"

born in 1999. PhD candidate. Member of CCF. Her main research interests include parallel computing and dynamic graph processing

"}, bioImg=null, bioContent=

born in 1999. PhD candidate. Member of CCF. Her main research interests include parallel computing and dynamic graph processing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495569505989589, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569254331344, language=CN, stringName=申玥, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
2中国科学院大学 北京 100049
3中关村实验室 北京 100094, bio={"img":"ijTsG5fYVy9WzS5h8romnA==","content":"

1999年生。博士研究生。CCF会员。主要研究方向为并行计算、动态图处理

"}, bioImg=ijTsG5fYVy9WzS5h8romnA==, bioContent=

1999年生。博士研究生。CCF会员。主要研究方向为并行计算、动态图处理

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])]), Author(id=1325495569585681367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495569682150361, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569585681367, language=EN, stringName=Jie Zhang, firstName=Jie, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, bio={"content":"

born in 1999. Master, assistant engineer. Her main research interests include high-performance computing and graph algorithm optimization

"}, bioImg=null, bioContent=

born in 1999. Master, assistant engineer. Her main research interests include high-performance computing and graph algorithm optimization

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495569782813658, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569585681367, language=CN, stringName=张婕, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190, bio={"img":"0mYsb7+Pg5lM9Z5+yCeeog==","content":"

1999年生。硕士,助理工程师。主要研究方向为高性能计算、图算法优化

"}, bioImg=0mYsb7+Pg5lM9Z5+yCeeog==, bioContent=

1999年生。硕士,助理工程师。主要研究方向为高性能计算、图算法优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)])]), Author(id=1325495569875088348, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zhangyuan-ams@ict.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1325495569988334558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569875088348, language=EN, stringName=Yuan Zhang, firstName=Yuan, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, bio={"content":"

born in 1990. PhD, engineer. Member of CCF. Her main research interests include high-performance computing and graph algorithm optimization

"}, bioImg=null, bioContent=

born in 1990. PhD, engineer. Member of CCF. Her main research interests include high-performance computing and graph algorithm optimization

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570088997855, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569875088348, language=CN, stringName=张园, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190, bio={"img":"kfNHDAnSggSAsCVsZHg+AA==","content":"

1990年生。博士,工程师。CCF 会员。主要研究方向为高性能计算、图算法优化

"}, bioImg=kfNHDAnSggSAsCVsZHg+AA==, bioContent=

1990年生。博士,工程师。CCF 会员。主要研究方向为高性能计算、图算法优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)])]), Author(id=1325495570164495329, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495570273547237, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570164495329, language=EN, stringName=Huawei Cao, firstName=Huawei, middleName=null, lastName=Cao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
2University of Chinese Academy of Sciences, Beijing 100049
3Zhongguancun Laboratory, Beijing 100094, bio={"content":"

born in 1989. PhD, associate professor, master supervisor. Member of CCF. His main research interests include parallel computing and high throughput computing architecture

"}, bioImg=null, bioContent=

born in 1989. PhD, associate professor, master supervisor. Member of CCF. His main research interests include parallel computing and high throughput computing architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570365821926, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570164495329, language=CN, stringName=曹华伟, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
2中国科学院大学 北京 100049
3中关村实验室 北京 100094, bio={"img":"lUnO3KE5AmRU3nnzgb1iEA==","content":"

1989年生。博士,副研究员,硕士生导师。CCF会员。主要研究方向为并行计算、高通量计算架构

"}, bioImg=lUnO3KE5AmRU3nnzgb1iEA==, bioContent=

1989年生。博士,副研究员,硕士生导师。CCF会员。主要研究方向为并行计算、高通量计算架构

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])]), Author(id=1325495570441319400, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495570537788396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570441319400, language=EN, stringName=Xuejun An, firstName=Xuejun, middleName=null, lastName=An, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
2University of Chinese Academy of Sciences, Beijing 100049
3Zhongguancun Laboratory, Beijing 100094, bio={"content":"

born in 1966. PhD, senior engineer, PhD supervisor. Member of CCF. His main research interests include computer system architecture and high-performance interconnection networks

"}, bioImg=null, bioContent=

born in 1966. PhD, senior engineer, PhD supervisor. Member of CCF. His main research interests include computer system architecture and high-performance interconnection networks

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570638451693, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570441319400, language=CN, stringName=安学军, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
2中国科学院大学 北京 100049
3中关村实验室 北京 100094, bio={"img":"+0vhILzGkOyww84GJW2RPA==","content":"

1966年生。博士,高级工程师,博士生导师。CCF会员。主要研究方向为计算机系统结构、高性能互连网络

"}, bioImg=+0vhILzGkOyww84GJW2RPA==, bioContent=

1966年生。博士,高级工程师,博士生导师。CCF会员。主要研究方向为计算机系统结构、高性能互连网络

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])]), Author(id=1325495570718143471, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495570823001073, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570718143471, language=EN, stringName=Xiaochun Ye, firstName=Xiaochun, middleName=null, lastName=Ye, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, bio={"content":"

born in 1981. PhD, professor, PhD supervisor. Member of CCF. His main research interests include algorithm paralleling and optimizing software simulation, and architecture for high throughput computer

"}, bioImg=null, bioContent=

born in 1981. PhD, professor, PhD supervisor. Member of CCF. His main research interests include algorithm paralleling and optimizing software simulation, and architecture for high throughput computer

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570902692850, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570718143471, language=CN, stringName=叶笑春, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190, bio={"img":"DyasaezD6eLTmEp/Aqs7+g==","content":"

1981年生。博士,研究员,博士生导师。CCF会员。主要研究方向为算法并行与优化软件仿真、高通量计算机体系结构

"}, bioImg=DyasaezD6eLTmEp/Aqs7+g==, bioContent=

1981年生。博士,研究员,博士生导师。CCF会员。主要研究方向为算法并行与优化软件仿真、高通量计算机体系结构

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)])])], keywords=[Keyword(id=1325495571041104883, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, orderNo=1, keyword=streaming graphs), Keyword(id=1325495571108213748, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, orderNo=2, keyword=incremental computation), Keyword(id=1325495571204682741, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, orderNo=3, keyword=dynamic graph processing), Keyword(id=1325495571292763126, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, orderNo=4, keyword=graph algorithms), Keyword(id=1325495571376649207, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, orderNo=5, keyword=parallel processing), Keyword(id=1325495571477312504, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, orderNo=6, keyword=graph processing systems), Keyword(id=1325495571557004281, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, orderNo=1, keyword=流式图), Keyword(id=1325495571636696058, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, orderNo=2, keyword=增量计算), Keyword(id=1325495571712193531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, orderNo=3, keyword=动态图处理), Keyword(id=1325495571804468220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, orderNo=4, keyword=图算法), Keyword(id=1325495573507355645, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, orderNo=5, keyword=并行处理), Keyword(id=1325495573624796158, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, orderNo=6, keyword=图处理系统)], refs=[Reference(id=1325495575650643984, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Berkhin P. A survey on PageRank computing[J]. Internet Mathematics, 2005, 2(1): 73−120, articleTitle=null, refAbstract=null), Reference(id=1325495575734530065, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Afarin M, Gao Chao, Rahman S, et al. CommonGraph: Graph analytics on evolving data[C]//Proc of the 28th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2023: 133−145, articleTitle=null, refAbstract=null), Reference(id=1325495575826804754, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Yu, Liang Yuxuan, Zhao Jin, et al. Egraph: Efficient concurrent GPU-based dynamic graph processing[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(6): 5823−5836, articleTitle=null, refAbstract=null), Reference(id=1325495575906496531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Han Wentao, Miao Youshan, Li Kaiwei, et al. Chronos: A graph engine for temporal graph analysis[C]//Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 1−14, articleTitle=null, refAbstract=null), Reference(id=1325495576007159828, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Miao Youshan, Han Wentao, Li Kaiwei, et al. Immortalgraph: A system for storage and analysis of temporal graphs[J]. ACM Transactions on Storage, 2015, 11(3): 1−34, articleTitle=null, refAbstract=null), Reference(id=1325495576124600341, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Vora K, Gupta R, Xu Guoqing. KickStarter: Fast and accurate computations on streaming graphs via trimmed approximations[C]//Proc of the 22nd Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2017: 237−251, articleTitle=null, refAbstract=null), Reference(id=1325495576221069334, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Mariappan M, Vora K. GraphBolt: Dependency-driven synchronous processing of streaming Graphs[C]//Proc of the 14th EuroSys Conf 2019. New York: ACM, 2019: 1−16, articleTitle=null, refAbstract=null), Reference(id=1325495577911373847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Iyer A P, Pu Qifan, Patel K, et al. TEGRA: Efficient ad-hoc analytics on evolving graphs[C]//Proc of the 18th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 337−355, articleTitle=null, refAbstract=null), Reference(id=1325495578007842840, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Dhankhad S, Mohammed E, Far B. Supervised machine learning algorithms for credit card fraudulent transaction detection: A comparative study[C]//Proc of the 19th IEEE Int Conf on Information Reuse and Integration (IRI). Piscataway, NJ: IEEE, 2018: 122−125, articleTitle=null, refAbstract=null), Reference(id=1325495578087534617, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Gupta P, Satuluri V, Grewal A, et al. Real-time Twitter recommendation: Online motif detection in large dynamic graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(13): 1379−1380, articleTitle=null, refAbstract=null), Reference(id=1325495578175615002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Kwak H, Lee C, Park H, et al. What is Twitter, a social network or a news media?[C]//Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 591−600, articleTitle=null, refAbstract=null), Reference(id=1325495578272083995, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Besta M, Fischer M, Kalavri V, et al. Practice of streaming processing of dynamic graphs: Concepts, models, and systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 34(6): 1860−1876, articleTitle=null, refAbstract=null), Reference(id=1325495578355970076, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=张园, 曹华伟, 张婕, 等. 面向多核CPU与GPU平台的图处理系统关键技术综述[J]. 计算机研究与发展, 2024, 61(6): 1401−1428, articleTitle=null, refAbstract=null), Reference(id=1325495578452439069, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Yuan, Cao Huawei, Zhang Jie, et al. Survey on key technologies of graph processing systems based on multi-core CPU and GPU platforms[J]. Journal of Computer Research and Development, 2024, 61(6): 1401−1428 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1325495578536325150, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Fan Wenfei, Tian Chao. Incremental graph computations: Doable and undoable[J]. ACM Transactions on Database Systems, 2022, 47(2): 1−44, articleTitle=null, refAbstract=null), Reference(id=1325495578620211231, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Beamer S, Asanović K, Patterson D. Direction optimizing breadth first search[J]. Scientific Programming, 2013, 21(3/4): 137−148, articleTitle=null, refAbstract=null), Reference(id=1325495578699903008, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Chakaravarthy V T, Checconi F, Murali P, et al. Scalable single source shortest path algorithms for massively parallel systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 28(7): 2031−2045, articleTitle=null, refAbstract=null), Reference(id=1325495578779594785, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Feng Guanyu, Ma Zixuan, Li Daixuan, et al. RisGraph: A real-time streaming system for evolving graphs to support sub-millisecond per update analysis at millions Ops/s[C]//Proc of the 48th Int Conf on Management of Data. New York: ACM, 2021: 513−527, articleTitle=null, refAbstract=null), Reference(id=1325495578888646690, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Jiang Xiaolin, Xu Chengshuo, Yin Xizhe, et al. Tripoline: Generalized incremental graph processing via graph triangle inequality[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 17−32, articleTitle=null, refAbstract=null), Reference(id=1325495579010281507, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Mariappan M, Che J, Vora K. DZIG: Sparsity-aware incremental processing of streaming graphs[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 83−98, articleTitle=null, refAbstract=null), Reference(id=1325495579085778980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Gong Shufeng, Tian Chao, Yin Qiang, et al. Ingress: An automated incremental graph processing system[J]. The VLDB Journal, 2024, 33(3): 781−806, articleTitle=null, refAbstract=null), Reference(id=1325495579182247973, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Murray D G, McSherry F, Isaacs R, et al. Naiad: A timely dataflow system[C]//Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 439−455, articleTitle=null, refAbstract=null), Reference(id=1325495579266134054, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Carbone P, Katsifodimos A, Ewen S, et al. Apache Flink: Stream and batch processing in a single engine[J]. The Bulletin of the Technical Committee on Data Engineering, 2015, 38(4): 28−38, articleTitle=null, refAbstract=null), Reference(id=1325495579366797351, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Xiaogang, Cui Bin, Shao Yingxia, et al. Tornado: A system for real-time iterative analysis over evolving data[C]//Proc of the 43rd Int Conf on Management of Data. New York: ACM, 2016: 417−430, articleTitle=null, refAbstract=null), Reference(id=1325495579438100520, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Toshniwal A, Taneja S, Shukla A, et al. Storm@ Twitter[C]//Proc of the 41st Int Conf on Management of Data. New York: ACM, 2014: 147−156, articleTitle=null, refAbstract=null), Reference(id=1325495579555541033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Dan, Gui Chuangyi, Zhang Yi, et al. GraphFly: Efficient asynchronous streaming graphs processing via dependency-flow[C]//Proc of the 35th Int Conf for High Performance Computing, Networking, Storage and Analysis. Piscataway, NJ: IEEE, 2022: 1−14, articleTitle=null, refAbstract=null), Reference(id=1325495579647815722, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Jiang Zihan, Mao Fubing, Guo Yapu, et al. ACGraph: Accelerating streaming graph processing via dependence hierarchy[C]//Proc of the 60th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2023: 1−6, articleTitle=null, refAbstract=null), Reference(id=1325495579777839147, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Valiant L G. A bridging model for parallel computation[J]. Communications of the ACM, 1990, 33(8): 103−111, articleTitle=null, refAbstract=null), Reference(id=1325495579891085356, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C]//Proc of the 37th Int Conf on Management of Data. New York: ACM, 2010: 135−146, articleTitle=null, refAbstract=null), Reference(id=1325495579966582829, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Shun Julian, Blelloch G E. Ligra: A lightweight graph processing framework for shared memory[C]//Proc of the 18th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2013: 135−146, articleTitle=null, refAbstract=null), Reference(id=1325495580084023342, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Kyrola A, Blelloch G, Guestrin C. GraphChi: Large-scale graph computation on just a PC[C]//Proc of the 10th USENIX Conf on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 31−46, articleTitle=null, refAbstract=null), Reference(id=1325495580159520815, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhu Xiaowei, Han Wentao, Chen Wenguang. GridGraph: Large scale graph processing on a single machine using 2-level hierarchical partitioning[C]//Proc of the 21st USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 375−386, articleTitle=null, refAbstract=null), Reference(id=1325495580251795504, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Low Y, Gonzalez J, Kyrola A, et al. GraphLab: A new framework for parallel machine learning[C]//Proc of the 26th Conf on Uncertainty in Artificial Intelligence. Arlington, Virginia: AUAI, 2010: 340−349, articleTitle=null, refAbstract=null), Reference(id=1325495580335681585, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Ediger D, McColl R, Riedy J, et al. Stinger: High performance data structure for streaming graphs[C]//Proc of the 16th IEEE Conf on High Performance Extreme Computing. Piscataway, NJ: IEEE, 2012: 1−5, articleTitle=null, refAbstract=null), Reference(id=1325495580411179059, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=Iscen A, Tolias G, Avrithis Y, et al. Label propagation for deep semi-supervised learning[C]//Proc of the 32nd IEEE/CVF Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2019: 1−10, articleTitle=null, refAbstract=null), Reference(id=1325495580499259444, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Chakrabarti D, Zhan Yiping, Faloutsos C. RMAT: A recursive model for graph mining[C]//Proc of the 4th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2004: 442−446, articleTitle=null, refAbstract=null), Reference(id=1325495580566368309, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Breiman L. Random forests[J]. Machine Learning, 2001, 45: 5−32, articleTitle=null, refAbstract=null), Reference(id=1325495580654448694, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Leiserson C E. The Cilk++ concurrency platform[C]//Proc of the 46th Annual Design Automation Conf. Piscataway, NJ: IEEE, 2009: 522−527, articleTitle=null, refAbstract=null), Reference(id=1325495580746723383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=Bader D A, Berry J, Kahan S, et al. Graph500[EB/OL]. 2010[2025-05-05]. http://www.graph500.org, articleTitle=null, refAbstract=null), Reference(id=1325495582395084856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=39, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Jaewon, Leskovec J. Defining and evaluating network communities based on ground-truth[C]//Proc of the 18th ACM SIGKDD Workshop on Mining Data Semantics. New York: ACM, 2012: 1−8, articleTitle=null, refAbstract=null), Reference(id=1325495582499942457, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=40, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=Takac L, Zabovsky M. Data analysis in public social networks[C/OL]//Proc of the Int Scientific Conf and Int Workshop Present Day Trends of Innovations. 2012[2025-05-05]. https://snap.stanford.edu/data/soc-pokec.pdf, articleTitle=null, refAbstract=null), Reference(id=1325495582768377914, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=41, rfOrder=41, authorNames=null, journalName=null, refType=null, unstructuredReference=Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1): 29−123, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])], figs=[ArticleFig(id=1325495573800956927, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 1, caption=Illustration of the iterative computation process of PageRank algorithm, figureFileSmall=H+HsyyE1U3jMVGFQZroUdg==, figureFileBig=TQx8NAWo4MId+3w39U/j8A==, tableContent=null), ArticleFig(id=1325495573910008832, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图1, caption=PageRank算法的迭代计算过程示意图, figureFileSmall=H+HsyyE1U3jMVGFQZroUdg==, figureFileBig=TQx8NAWo4MId+3w39U/j8A==, tableContent=null), ArticleFig(id=1325495574128111616, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 2, caption=Experimental comparative analysis of incremental computing models based on correction and recalculation, figureFileSmall=jnOY8vstDtAZR9sLh07lQw==, figureFileBig=M5u41TP7JgEwI/QtycmwNQ==, tableContent=null), ArticleFig(id=1325495574211997697, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图2, caption=基于修正和重计算的增量计算模式的实验对比分析, figureFileSmall=jnOY8vstDtAZR9sLh07lQw==, figureFileBig=M5u41TP7JgEwI/QtycmwNQ==, tableContent=null), ArticleFig(id=1325495574279106562, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 3, caption=Performance comparison of four computation modes on RMAT dataset with varied scales of vertex, figureFileSmall=/8ktH79klmdRg/or4jm0KA==, figureFileBig=v/aJzyNQSVNmKAfsWQXJ3w==, tableContent=null), ArticleFig(id=1325495574358798339, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图3, caption=4种计算模式在不同顶点规模的RMAT数据集上的性能比较, figureFileSmall=/8ktH79klmdRg/or4jm0KA==, figureFileBig=v/aJzyNQSVNmKAfsWQXJ3w==, tableContent=null), ArticleFig(id=1325495574442684420, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 4, caption=Performance comparison of four computation modes on RMAT dataset with varied average degrees, figureFileSmall=uJzq/hGDODEA8Cj7kq8LZg==, figureFileBig=eWWHe8vqm0s5R/4ozn9shQ==, tableContent=null), ArticleFig(id=1325495574509793285, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图4, caption=4种计算模式在不同平均度数的RMAT数据集上的性能比较, figureFileSmall=uJzq/hGDODEA8Cj7kq8LZg==, figureFileBig=eWWHe8vqm0s5R/4ozn9shQ==, tableContent=null), ArticleFig(id=1325495574623039494, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 5, caption=Performance comparison of four computation modes on RMAT_25_16 when |ΔG| varies, figureFileSmall=TzOSmNK9PWC+ZXISLxnueA==, figureFileBig=nHTPLu1edutHUTl9yCXBPg==, tableContent=null), ArticleFig(id=1325495574715314183, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图5, caption=当|ΔG|变化时4种计算模式在RMAT_25_16上的性能比较, figureFileSmall=TzOSmNK9PWC+ZXISLxnueA==, figureFileBig=nHTPLu1edutHUTl9yCXBPg==, tableContent=null), ArticleFig(id=1325495574845337608, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 6, caption=Switching effect analysis of IncHybrid mode, figureFileSmall=ZcVBV3TQBazEr3qFHyf6Tg==, figureFileBig=RPGjoxazZ+nKsVxyt2OS0Q==, tableContent=null), ArticleFig(id=1325495574946000905, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图6, caption=IncHybrid模式的切换效果分析, figureFileSmall=ZcVBV3TQBazEr3qFHyf6Tg==, figureFileBig=RPGjoxazZ+nKsVxyt2OS0Q==, tableContent=null), ArticleFig(id=1325495575042469898, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Figure 7, caption=Performance comparison of four computation modes on the real-world datasets, figureFileSmall=Ug1IYLtgo8aZ5tIGWFagSA==, figureFileBig=P/cTGvnbooxuWdmFylAK1Q==, tableContent=null), ArticleFig(id=1325495575164104715, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=图7, caption=4种计算模式在真实图数据集上的性能比较, figureFileSmall=Ug1IYLtgo8aZ5tIGWFagSA==, figureFileBig=P/cTGvnbooxuWdmFylAK1Q==, tableContent=null), ArticleFig(id=1325495575252185100, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Table 1, caption=Fourteen Graph Datasets Used in the Experiment, figureFileSmall=null, figureFileBig=null, tableContent=
数据集顶点数量边数量
注:$ S $表示图数据集的规模(顶点数量为$ {2}^{S} $),$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $表示图数据集的平均度数.
RMAT_$ S $_$ 16 $(共6个,$ S\in \left\{ {20,21,22,23,24,25}\right\} $)$ {2}^{S} $$ {2}^{S}\times 16 $
RMAT_$ 24 $_$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $(共3个,$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}}\in \left\{\mathrm{10,13,19}\right\} $)$ {2}^{24} $$ {2}^{24}\times {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $
LJ3 997 96234 681 189
OR3 072 441117 185 083
PK1 632 80330 622 564
CA1 965 2062 766 607
TX1 379 9171 921 660
), ArticleFig(id=1325495575357042701, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=表1, caption=

实验所采用的14个图数据集

, figureFileSmall=null, figureFileBig=null, tableContent=
数据集顶点数量边数量
注:$ S $表示图数据集的规模(顶点数量为$ {2}^{S} $),$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $表示图数据集的平均度数.
RMAT_$ S $_$ 16 $(共6个,$ S\in \left\{ {20,21,22,23,24,25}\right\} $)$ {2}^{S} $$ {2}^{S}\times 16 $
RMAT_$ 24 $_$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $(共3个,$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}}\in \left\{\mathrm{10,13,19}\right\} $)$ {2}^{24} $$ {2}^{24}\times {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $
LJ3 997 96234 681 189
OR3 072 441117 185 083
PK1 632 80330 622 564
CA1 965 2062 766 607
TX1 379 9171 921 660
), ArticleFig(id=1325495575449317390, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=EN, label=Table 2, caption=Execution Time and Speedup of IncHybrid Mode and DZIG System, figureFileSmall=null, figureFileBig=null, tableContent=

算法
执行时间/sIncHybrid模式相比DZIG系统的加速比
DZIG系统IncHybrid模式(本文)
212223242122232421222324
PageRank1.0141.6062.7046.5380.5271.0182.5686.3021.921.581.051.04
Label Propagation2.3304.1177.44414.9952.3534.1627.36112.6740.990.991.011.18
BFS0.0320.0680.1500.2750.0290.0490.0950.2171.101.391.581.27
SSSP0.0370.0710.1530.3290.0330.0570.1150.2521.121.251.331.31
), ArticleFig(id=1325495575524814863, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, language=CN, label=表2, caption=

IncHybrid模式与DZIG系统的执行时间和加速比

, figureFileSmall=null, figureFileBig=null, tableContent=

算法
执行时间/sIncHybrid模式相比DZIG系统的加速比
DZIG系统IncHybrid模式(本文)
212223242122232421222324
PageRank1.0141.6062.7046.5380.5271.0182.5686.3021.921.581.051.04
Label Propagation2.3304.1177.44414.9952.3534.1627.36112.6740.990.991.011.18
BFS0.0320.0680.1500.2750.0290.0490.0950.2171.101.391.581.27
SSSP0.0370.0710.1530.3290.0330.0570.1150.2521.121.251.331.31
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550151, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550151, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202550151, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202550151, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1772294400000, fullTextJson=null, articleText=null, reference=null)
收藏切换
基于混合增量计算的流式图并行处理
申玥 1, 2, 3 , 张婕 1 , 张园 1, * , 曹华伟 1, 2, 3 , 安学军 1, 2, 3 , 叶笑春 1
计算机研究与发展 | 高性能计算 2026,63(3): 798-811
收起
收藏切换
计算机研究与发展 |高性能计算 2026 , 63 (3) : 798 -811
基于混合增量计算的流式图并行处理
全屏
[Author(id=1325495569254331344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=shenyue24b@ict.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495569388549076, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569254331344, language=EN, stringName=Yue Shen, firstName=Yue, middleName=null, lastName=Shen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
2University of Chinese Academy of Sciences, Beijing 100049
3Zhongguancun Laboratory, Beijing 100094, bio={"content":"

born in 1999. PhD candidate. Member of CCF. Her main research interests include parallel computing and dynamic graph processing

"}, bioImg=null, bioContent=

born in 1999. PhD candidate. Member of CCF. Her main research interests include parallel computing and dynamic graph processing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495569505989589, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569254331344, language=CN, stringName=申玥, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
2中国科学院大学 北京 100049
3中关村实验室 北京 100094, bio={"img":"ijTsG5fYVy9WzS5h8romnA==","content":"

1999年生。博士研究生。CCF会员。主要研究方向为并行计算、动态图处理

"}, bioImg=ijTsG5fYVy9WzS5h8romnA==, bioContent=

1999年生。博士研究生。CCF会员。主要研究方向为并行计算、动态图处理

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])]), Author(id=1325495569585681367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495569682150361, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569585681367, language=EN, stringName=Jie Zhang, firstName=Jie, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, bio={"content":"

born in 1999. Master, assistant engineer. Her main research interests include high-performance computing and graph algorithm optimization

"}, bioImg=null, bioContent=

born in 1999. Master, assistant engineer. Her main research interests include high-performance computing and graph algorithm optimization

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495569782813658, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569585681367, language=CN, stringName=张婕, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190, bio={"img":"0mYsb7+Pg5lM9Z5+yCeeog==","content":"

1999年生。硕士,助理工程师。主要研究方向为高性能计算、图算法优化

"}, bioImg=0mYsb7+Pg5lM9Z5+yCeeog==, bioContent=

1999年生。硕士,助理工程师。主要研究方向为高性能计算、图算法优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)])]), Author(id=1325495569875088348, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zhangyuan-ams@ict.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1325495569988334558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569875088348, language=EN, stringName=Yuan Zhang, firstName=Yuan, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, bio={"content":"

born in 1990. PhD, engineer. Member of CCF. Her main research interests include high-performance computing and graph algorithm optimization

"}, bioImg=null, bioContent=

born in 1990. PhD, engineer. Member of CCF. Her main research interests include high-performance computing and graph algorithm optimization

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570088997855, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495569875088348, language=CN, stringName=张园, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190, bio={"img":"kfNHDAnSggSAsCVsZHg+AA==","content":"

1990年生。博士,工程师。CCF 会员。主要研究方向为高性能计算、图算法优化

"}, bioImg=kfNHDAnSggSAsCVsZHg+AA==, bioContent=

1990年生。博士,工程师。CCF 会员。主要研究方向为高性能计算、图算法优化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)])]), Author(id=1325495570164495329, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495570273547237, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570164495329, language=EN, stringName=Huawei Cao, firstName=Huawei, middleName=null, lastName=Cao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
2University of Chinese Academy of Sciences, Beijing 100049
3Zhongguancun Laboratory, Beijing 100094, bio={"content":"

born in 1989. PhD, associate professor, master supervisor. Member of CCF. His main research interests include parallel computing and high throughput computing architecture

"}, bioImg=null, bioContent=

born in 1989. PhD, associate professor, master supervisor. Member of CCF. His main research interests include parallel computing and high throughput computing architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570365821926, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570164495329, language=CN, stringName=曹华伟, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
2中国科学院大学 北京 100049
3中关村实验室 北京 100094, bio={"img":"lUnO3KE5AmRU3nnzgb1iEA==","content":"

1989年生。博士,副研究员,硕士生导师。CCF会员。主要研究方向为并行计算、高通量计算架构

"}, bioImg=lUnO3KE5AmRU3nnzgb1iEA==, bioContent=

1989年生。博士,副研究员,硕士生导师。CCF会员。主要研究方向为并行计算、高通量计算架构

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])]), Author(id=1325495570441319400, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495570537788396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570441319400, language=EN, stringName=Xuejun An, firstName=Xuejun, middleName=null, lastName=An, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
2University of Chinese Academy of Sciences, Beijing 100049
3Zhongguancun Laboratory, Beijing 100094, bio={"content":"

born in 1966. PhD, senior engineer, PhD supervisor. Member of CCF. His main research interests include computer system architecture and high-performance interconnection networks

"}, bioImg=null, bioContent=

born in 1966. PhD, senior engineer, PhD supervisor. Member of CCF. His main research interests include computer system architecture and high-performance interconnection networks

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570638451693, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570441319400, language=CN, stringName=安学军, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
2中国科学院大学 北京 100049
3中关村实验室 北京 100094, bio={"img":"+0vhILzGkOyww84GJW2RPA==","content":"

1966年生。博士,高级工程师,博士生导师。CCF会员。主要研究方向为计算机系统结构、高性能互连网络

"}, bioImg=+0vhILzGkOyww84GJW2RPA==, bioContent=

1966年生。博士,高级工程师,博士生导师。CCF会员。主要研究方向为计算机系统结构、高性能互连网络

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)]), AuthorCompany(id=1325495569015256009, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=2, ext=[AuthorCompanyExt(id=1325495569027838922, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1325495569036227531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569015256009, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国科学院大学 北京 100049)]), AuthorCompany(id=1325495569128502220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=3, ext=[AuthorCompanyExt(id=1325495569141085133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Zhongguancun Laboratory, Beijing 100094), AuthorCompanyExt(id=1325495569153668046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495569128502220, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中关村实验室 北京 100094)])]), Author(id=1325495570718143471, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1325495570823001073, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570718143471, language=EN, stringName=Xiaochun Ye, firstName=Xiaochun, middleName=null, lastName=Ye, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, bio={"content":"

born in 1981. PhD, professor, PhD supervisor. Member of CCF. His main research interests include algorithm paralleling and optimizing software simulation, and architecture for high throughput computer

"}, bioImg=null, bioContent=

born in 1981. PhD, professor, PhD supervisor. Member of CCF. His main research interests include algorithm paralleling and optimizing software simulation, and architecture for high throughput computer

, aboutCorrespAuthor=null), CN=AuthorExt(id=1325495570902692850, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, authorId=1325495570718143471, language=CN, stringName=叶笑春, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190, bio={"img":"DyasaezD6eLTmEp/Aqs7+g==","content":"

1981年生。博士,研究员,博士生导师。CCF会员。主要研究方向为算法并行与优化软件仿真、高通量计算机体系结构

"}, bioImg=DyasaezD6eLTmEp/Aqs7+g==, bioContent=

1981年生。博士,研究员,博士生导师。CCF会员。主要研究方向为算法并行与优化软件仿真、高通量计算机体系结构

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1325495567308174278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, xref=1, ext=[AuthorCompanyExt(id=1325495567316562887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190), AuthorCompanyExt(id=1325495567324951496, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1325495561905910697, companyId=1325495567308174278, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)])])]
申玥1, 2, 3 , 张婕1, 张园1, * , 曹华伟1, 2, 3, 安学军1, 2, 3, 叶笑春1
作者信息
  • 1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
  • 2中国科学院大学 北京 100049
  • 3中关村实验室 北京 100094
通讯作者:
作者简介:

1999年生。博士研究生。CCF会员。主要研究方向为并行计算、动态图处理

1999年生。硕士,助理工程师。主要研究方向为高性能计算、图算法优化

1990年生。博士,工程师。CCF 会员。主要研究方向为高性能计算、图算法优化

1989年生。博士,副研究员,硕士生导师。CCF会员。主要研究方向为并行计算、高通量计算架构

1966年生。博士,高级工程师,博士生导师。CCF会员。主要研究方向为计算机系统结构、高性能互连网络

1981年生。博士,研究员,博士生导师。CCF会员。主要研究方向为算法并行与优化软件仿真、高通量计算机体系结构

Parallel Streaming Graph Processing with Hybrid Incremental Computation
Yue Shen1, 2, 3 , Jie Zhang1, Yuan Zhang1, * , Huawei Cao1, 2, 3, Xuejun An1, 2, 3, Xiaochun Ye1
Affiliations
  • 1State Key Laboratory of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190
  • 2University of Chinese Academy of Sciences, Beijing 100049
  • 3Zhongguancun Laboratory, Beijing 100094
  • born in 1999. PhD candidate. Member of CCF. Her main research interests include parallel computing and dynamic graph processing

    born in 1999. Master, assistant engineer. Her main research interests include high-performance computing and graph algorithm optimization

    born in 1990. PhD, engineer. Member of CCF. Her main research interests include high-performance computing and graph algorithm optimization

    born in 1989. PhD, associate professor, master supervisor. Member of CCF. His main research interests include parallel computing and high throughput computing architecture

    born in 1966. PhD, senior engineer, PhD supervisor. Member of CCF. His main research interests include computer system architecture and high-performance interconnection networks

    born in 1981. PhD, professor, PhD supervisor. Member of CCF. His main research interests include algorithm paralleling and optimizing software simulation, and architecture for high throughput computer

出版时间: 2026-03-01 doi: 10.7544/issn1000-1239.202550151
文章导航
收藏切换

流式图能够对现实生活中数据快速变化的场景进行有效建模,在社交网络分析、内容推荐、异常检测等领域得到了广泛应用。基于流式图更新前后的2个图快照具有大量相同数据的事实,增量计算通过对历史计算结果进行存储和复用来降低迭代计算过程中的访存量和计算量,从而有效提升流式图处理的性能。然而,现有对图算法进行增量计算优化的研究往往受限于满足特定性质的图算法,而难以应用于通用图算法。针对通用图算法的增量计算优化问题,将增量计算进一步划分为基于修正和基于重计算的增量计算模式。理论上刨析了二者的异同点,实验上在不同图数据集、图算法和更新场景设置下测试了二者的性能差异。提出了混合增量计算模式,设计了确保切换正确性的算法,并通过随机森林分类器准确地预测切换时机。性能评估和切换效果分析表明通用图算法在混合增量计算模式下能够进行有效切换,并相比先进的流式图处理系统DZIG实现了平均1.25的加速比。

流式图  /  增量计算  /  动态图处理  /  图算法  /  并行处理  /  图处理系统

Streaming graphs can effectively model rapidly changing data in real life, and have been widely used in social network analysis, content recommendation, anomaly detection, and other fields. Based on the fact that the two graph snapshots before and after the graph update have a large amount of the same data, incremental computation reduces the amount of memory accesses and computation in the iterations by storing and reusing the historical results, which effectively improves the performance of streaming graph processing. However, the existing solutions for incremental computation optimization of graph algorithms are often limited by graph algorithms that satisfy specific properties, thus it is difficult to apply them to general graph algorithms. In this paper, the incremental computation is further divided into two modes of refinement and recomputation. The similarities and differences between the two modes are analyzed theoretically, and the performance differences between them are tested experimentally with different datasets, algorithms, and update settings. Based on the two modes, the hybrid incremental computation mode is designed to ensure the correctness of switching, and the switching time is predicted accurately by random forest classifiers. Through performance evaluation and switching effect analysis, it is proved that the general graph algorithms can effectively switch under the hybrid mode. Compared with the state-of-the-art solution DZIG, the average speedup is 1.25.

streaming graphs  /  incremental computation  /  dynamic graph processing  /  graph algorithms  /  parallel processing  /  graph processing systems
申玥, 张婕, 张园, 曹华伟, 安学军, 叶笑春. 基于混合增量计算的流式图并行处理. 计算机研究与发展, 2026 , 63 (3) : 798 -811 . DOI: 10.7544/issn1000-1239.202550151
Yue Shen, Jie Zhang, Yuan Zhang, Huawei Cao, Xuejun An, Xiaochun Ye. Parallel Streaming Graph Processing with Hybrid Incremental Computation[J]. Journal of Computer Research and Development, 2026 , 63 (3) : 798 -811 . DOI: 10.7544/issn1000-1239.202550151
图作为一种非线性数据结构,凭借其对数据的强大建模能力,在各行业领域得到了广泛的应用。其由顶点集和边集构成,顶点和边分别用来表示实体以及实体之间的关系。例如,对于微博社交网络图,用户被表示成顶点,而用户间的关注或评论被表示成边。 现实世界中的图数据往往具有动态性,对动态图进行处理可以得到蕴含时间信息的查询结果。例如,在微博社交网络图上执行PageRank[1]算法,可以得到微博用户影响力在一段时间内的变化情况,亦可以求得实时的用户影响力。根据上述2种查询结果,动态图处理可以被粗粒度地划分为演化图处理(evolving graph processing)和流式图处理(streaming graph processing)两个研究领域[2]。前者处理的是不同时间窗口的多个图快照,目标是得到查询结果随时间的变化情况[3-5];而后者处理的是一个不断更新的图快照,目标是得到最新的查询结果[6-8]。本文研究的是流式图处理领域的相关理论和技术。
对流式图进行处理需要在图数据变化的过程中持续进行计算,以不断更新查询结果。流式图处理在许多对查询结果实时性要求较高的应用中至关重要,例如异常检测[9]、内容推荐[10]和社交网络分析[11]等。工业界和学术界处理流式图的技术主要包括传统计算(traditional computation)和增量计算(incremental computation)[12-13]。传统计算即静态图处理领域采用的计算技术,也称为全计算(full computation)。相比传统计算,增量计算通过存储并复用历史计算结果有效地减少了计算量和访存量[14],从而具有更优的性能。近年来,针对增量计算的研究主要集中在单调类图算法(在迭代计算过程中顶点状态值单调递减或者递增,如宽度优先搜索[15](breadth first search,BFS)和单源最短路径[16](single source shortest path,SSSP)算法)优化[6,17-18]和支持通用图算法的增量计算[7,19-20]这2个方面。然而,对单调类图算法的专用优化技术不能应用于其他非单调类图算法(如PageRank算法),而支持通用图算法的研究主要集中在系统级功能开发和性能优化上。因此,现有方法难以在算法层面有效提升通用图算法的增量计算性能。
我们观察到,根据对受更新影响顶点处理方式的不同,增量计算可以进一步划分为基于修正的增量计算模式和基于重计算的增量计算模式。通过对二者进行理论上的对比分析,我们发现2种增量计算模式具有诸多差异。基于修正的增量计算模式通过推送(push)方式[15]访问出射邻居顶点,从而精确触发受更新影响的顶点修正聚合值和顶点状态值,并且需要原子操作处理数据冲突;而基于重计算的增量计算模式采用拉取(pull)方式[15]访问所有的入射邻居顶点,并据此为受更新影响的顶点重新计算顶点状态值,在这一过程中没有数据冲突。我们进一步对二者进行实验上的对比分析,发现当数据集顶点规模、平均度数、更新边流大小和图算法改变时,2种增量计算模式在每轮迭代计算存在着性能差异。因此,在图算法迭代计算过程中,通过选择2种增量计算模式中性能更优的模式能够提升增量计算性能。但是,实现该目标具有以下2个挑战:
1)如何保证切换的正确性。2种增量计算模式在迭代计算过程中对邻居顶点的访问方式、更新边流的处理方法以及顶点状态值的计算方式等均不相同,难以在2种模式之间搭建桥梁实现正确切换。
2)如何准确预测切换的时机。不准确的切换时机不仅会降低切换带来的性能增益,甚至还会错误地切换到性能较差的模式,最终延长算法的执行时间。
针对上述挑战,本文提出了基于混合增量计算模式的流式图并行处理,主要贡献包括3个方面:
1)分别阐述了基于修正和基于重计算的增量计算模式的原理,并进行了实验和理论上的对比分析。
2)提出了混合增量计算模式,能够对2种增量计算模式进行正确切换,并通过随机森林分类器实现了准确切换。
3)代码实现了本文提出的理论方法,并进行了实验评估。实验结果表明,混合增量计算模式能够有效提升增量计算的性能,相比先进的流式图处理系统DZIG[19]实现了平均1.25的加速比。
对流式图进行分析可以得到实时的查询结果,国内外学术界和工业界围绕流式图处理领域开展了一系列研究工作,开发了一些具有代表性的经典系统。
早期的相关研究主要集中在通用的数据流处理系统,代表工作有Naiad[21],Flink[22],Tornado[23],这些系统不局限于处理流式图数据。Naiad[21]是微软公司在2013年提出的分布式数据流处理系统,同时支持批处理和流处理,它的一大特色是采用了差分数据流支持增量计算,实现了对历史数据的复用。Flink[22]是2015年提出的Apache开源项目,提供了支持批处理和流处理的应用程序编程接口,并支持运行多种图算法。Tornado[23]是北京大学在2016年基于Storm[24]开发的系统,其将迭代计算过程划分为维护近似计算结果的主循环和产生实时计算结果的分支循环,从而通过增量计算加快收敛。这些通用的数据流处理系统没有针对流式图数据进行专门优化。
近年来,部分流式图处理系统针对单调类图算法的特性进行了专门的优化。KickStarter[6]由加州大学河滨分校在2017年提出,其通过对所维护的依赖关系树进行剪枝来实现增量计算。清华大学在2021年沿用KickStarter的思想开发了RisGraph[17],其对数据结构、并行模式和吞吐量等进行了系统优化。加州大学河滨分校在2021年提出了Tripoline[18],其提出的图三角形不等式解决了单调类图算法在源顶点改变后难以进行增量计算的问题。华中科技大学在2022年和2023年分别提出了GraphFly[25]和ACGraph[26],GraphFly基于依赖树划分流式图并根据时空约束异步地处理分块,ACGraph则通过分析删增边的依赖关系规范顶点的处理顺序,二者均有效降低了增量计算中的冗余访存量和计算量。这些系统虽然实现了较高的流式图处理性能,但只局限于运行单调类图算法。
另外一些流式图处理系统提供了运行单调类和非单调类图算法的能力。GraphBolt[7]由西蒙菲莎大学在 2019 年提出,其在初始计算阶段对每轮迭代计算产生的计算结果进行存储,之后在增量计算阶段根据更新边流信息修正所存储的历史计算结果,相比传统计算模式有效地降低了计算量和访存量。为了进一步提升GraphBolt的计算性能,西蒙菲莎大学进一步在2021年提出了DZIG[19],其为GraphBolt引入了稀疏感知能力,只有当顶点$ v $前后2轮迭代计算的顶点状态值的变化量超过自定义阈值时,顶点$ v $才将该变化量传播(propagate)给它的出射邻居顶点,从而减少修正操作。虽然上述系统支持通用图算法的增量计算,但其仅使用了单一的增量计算模式,并未探究采用其他增量计算模式进一步提升计算性能的可能性。
图$ G=(V,E) $是由顶点和边组成的数据结构,其中$ V $和$ E $分别表示顶点集和边集。设图$ G $中有$ n $个顶点和$ m $条边,则顶点集和边集可分别表示为$ V= \{{v}_{1}, {v}_{2}, … , {v}_{n}\} $和$ E= \{{e}_{1},{e}_{2}, … ,{e}_{m}\} $。
流式图是一种动态图,其结构随着源源不断的更新边流(边的插入或删除)的到来而持续变化。流式图处理包括图更新和图计算2个阶段。在图更新阶段,更新边流集合$ {\Delta }G $被摄入图$ G $中,形成更新后的图$ {G'}= ({V'},{E'}) $。在图计算阶段,图算法在更新后的图$ {G'} $上执行,计算出图数据变化后的查询结果。随着源源不断的更新边流的到来,流式图的更新和计算持续交替进行,以得到最新的查询结果。
整体同步并行(bulk synchronous parallel,BSP)[27]是一种经典的同步并行计算模型,其将并行计算过程抽象为多个超步(superstep),在每个超步中完成计算、通信和同步3个阶段的任务,达到超步数量上限或满足终止条件时停止计算。2010年,谷歌公司基于BSP模型提出了最早的图处理系统Pregel[28]。此后,BSP模型因其易编程性在图计算领域被广泛使用。
接下来介绍基于BSP的以顶点为中心(vertex-centric)的迭代计算模型。该模型将迭代图算法中的1轮迭代计算与1个超步相对应,在每轮迭代计算的过程中,以顶点为并行计算单元,各顶点通过访问上一轮迭代计算中其邻居顶点和自身的顶点状态值来完成本轮迭代计算中顶点状态值的计算和更新。由于各顶点的邻居顶点数量不同,故每个顶点的任务量亦不相同,在完成每一轮迭代计算的顶点状态值计算后,参与计算的顶点(即活跃顶点)要进行1次同步。
本文参考经典静态图处理框架Ligra[29],将每轮迭代计算的过程进一步划分为边计算和点计算2个阶段,并通过引入活跃顶点(frontiers)集合过滤掉不需要参与计算的顶点(在每轮迭代计算中只需对活跃顶点进行处理)。在边计算阶段,各顶点根据接收到的活跃的入射邻居顶点信息计算聚合值(aggregation values);在点计算阶段,各顶点根据聚合值完成顶点状态值的计算和更新。边计算阶段对邻居顶点的访问可以通过以下2种方式完成:
1)推送方式。各顶点将其上一轮迭代计算的顶点值推送给出射邻居顶点,其出射邻居顶点被动地完成本轮迭代计算的顶点值的计算和更新。当多个顶点(被分配给多个线程)同时更新同一个出射邻居顶点时,推送方式会造成写冲突。
2)拉取方式。各顶点拉取入射邻居顶点上一轮迭代计算的顶点值,主动地完成本轮迭代计算的自身顶点值的计算和更新。由于只有该顶点自身(被分配给1个线程)能更新其顶点值,拉取方式不会造成写冲突。
传统计算模式即静态图处理领域采用的计算模式[29-32],也被用于流式图处理领域[33]。其不对更新前的图$ G $上的历史计算结果进行存储和复用,而是在更新后的图$ {G'} $上,直接从算法给定的初始值开始进行迭代计算。
设$ {D}_{i}=\left\{{d}_{i}\left({v}_{1}\right),{d}_{i}\left({v}_{2}\right), … ,{d}_{i}\left({v}_{n}\right)\right\} $和$ {G}_{i} = \{{g}_{i}\left({v}_{1}\right),{g}_{i}\left({v}_{2}\right), … ,{g}_{i}\left({v}_{n}\right) \} $分别表示$ n $个顶点在第$ i $轮迭代计算中的顶点状态值和聚合值构成的集合,而$ {D}_{0} $和$ {G}_{0} $分别表示初始顶点状态值和初始聚合值构成的集合。例如在PageRank算法中,所有顶点的初始顶点状态值为$ 1 $,初始聚合值为0。传统计算模式可以用式(1)表示。
$ {D}_{i}={f}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{d}}\left({D}_{i-1}\right) \text{,} $
其中映射$ {f}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{d}} $由采用了传统计算模式的特定图算法定义。
设$ {d}_{i}\left(v\right) $表示顶点$ v $在第$ i $轮迭代计算结束后的顶点状态值,$ {N}_{\mathrm{i}\mathrm{n}}\left(v\right) $和$ {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}\left(v\right) $分别表示顶点$ v $的入射和出射邻居构成的集合,$ {F}_{i} $表示第$ i $轮迭代计算的活跃顶点集合,则边计算过程可表示为
$ {A}_{i}\left(v\right)={F}_{i}\cap {N}_{\mathrm{i}\mathrm{n}}\left(v\right) \text{,} $
$ {g}_{i}\left(v\right)=\underset{u\in {A}_{i}\left(v\right)}{\oplus}\left({d}_{i-1}\left(u\right)\right)\text{,} $
其中$ {A}_{i}\left(v\right) $表示顶点$ v $在第$ i $轮迭代计算中活跃的入射邻居顶点,$ \oplus $表示聚合算子,$ {g}_{i}\left(v\right) $表示顶点$ v $在第$ i $轮迭代计算的聚合值。对于PageRank算法,$ {g}_{i}\left(v\right) = \displaystyle\sum _{u\in {A}_{i}\left(v\right)} \dfrac{{d}_{i-1}\left(u\right)}{outDegree\left(u\right)} $。
而点计算阶段则包括2个步骤,首先顶点$ v $根据聚合值$ {g}_{i}\left(v\right) $计算出新的顶点状态值$ {d}_{\mathrm{n}\mathrm{e}\mathrm{w}}\left(v\right) $,之后判断是否对上一轮迭代计算的顶点状态值$ {d}_{i-1}\left(v\right) $进行更新,该过程可以表示为
$ {d}_{\mathrm{n}\mathrm{e}\mathrm{w}}\left(v\right)=\displaystyle\oint {g}_{i}\left(v\right) \text{,} $
$ {d}_{i}\left(v\right)=upt\left({d}_{i-1}\left(v\right),{d}_{\mathrm{n}\mathrm{e}\mathrm{w}}\left(v\right)\right)\text{,} $
其中$ \displaystyle\oint $表示顶点状态值计算算子,在PageRank算法中,$ \displaystyle\oint {g}_{i}\left(v\right)= 1-d+d\times {g}_{i}\left(v\right) $($ d $为阻尼系数)。$ upt(\cdot ) $表示更新算子,若新的顶点状态值$ {d}_{\mathrm{n}\mathrm{e}\mathrm{w}}\left(v\right) $满足特定算法的更新条件则更新顶点状态值。在PageRank算法中,若$ \left|{d}_{\mathrm{n}\mathrm{e}\mathrm{w}}\right(v) -{d}_{i-1}(v\left)\right| \gt \epsilon $($ \epsilon $为更新阈值),则$ {d}_{i}\left(v\right)={d}_{\mathrm{n}\mathrm{e}\mathrm{w}}\left(v\right) $,否则$ {d}_{i}\left(v\right)={d}_{i-1}\left(v\right) $。本文将代码实现的传统计算模式称为Tradition模式。
在流式图处理中,更新边流的大小(表示为$ \left|{\Delta }G\right| $)相比更新前的图大小(表示为$ \left|G\right| $)占比较小,这意味着更新前后的2个图快照中存在大量相同的顶点和边[14]。因此,当采用传统计算模式对更新前后的2个图快照进行处理时,在边计算阶段会访问大量相同的邻居顶点并计算相同的聚合值,而在点计算阶段则会计算相同的顶点状态值。与传统计算模式不同,增量计算模式在处理更新前的图快照时对产生的计算结果进行了存储,而在处理更新后的图快照时则复用历史计算结果,从而避免了冗余的计算和访存操作。
根据对受更新影响的顶点的处理方式的不同,本文将增量计算进一步划分为基于修正的增量计算模式和基于重计算的增量计算模式。
基于修正的增量计算模式被大多数先进的流式图处理系统采用[6-7,17-20],其在图$ G $上进行迭代计算的过程中,对每轮迭代计算的历史计算结果进行存储,之后在更新后的图$ {G'} $上进行迭代计算时,通过修正所存储的历史计算结果得到最新的计算结果。通过修正,该模式的计算结果与采用传统计算模式得到的计算结果完全一致。
设 $ {D}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\;=\; \{{d}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left({v}_{1}\right),\;{d}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left({v}_{2}\right),\; … ,\;{d}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left({v}_{n}\right)\} $ 和 $ {G}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}= \{{g}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}} \left({v}_{1}\right), {g}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left({v}_{2}\right), … ,{g}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left({v}_{n}\right)\} $分别表示$ n $个顶点在历史第$ i $轮迭代计算中的顶点状态值集合和聚合值构成的集合。基于修正的增量计算模式可以用式(6)表达。
$ ({D}_{i},{G}_{i}) ={f}_{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}({D}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}},{G}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}},{D}_{i-1}) \text{,} $
其中映射$ {f}_{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $由采用了基于修正的增量计算模式的特定图算法定义。下面对边计算和点计算阶段进行介绍。
在边计算阶段,受更新边流集合$ {\Delta }G $影响的顶点(对于PageRank算法,顶点状态值或出度发生改变),必须作为活跃顶点参与边计算,并以推送方式触发出射邻居顶点修正历史顶点状态值,不受更新影响的其他顶点则不需要参与边计算。设$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $表示基于修正的增量计算模式在第$ i $轮迭代计算的活跃顶点集合,$ {T}_{i} $表示第$ i $轮迭代计算中须要修正顶点状态值的顶点构成的集合,则有
$ {T}_{i}=\left\{v\right|\left(u,v\right)\in {E'},u\in {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}\} \;。$
设$ {R}_{i}\left(v\right) $表示第$ i $轮迭代计算中触发顶点$ v $进行边计算的入射邻居集合,则边计算阶段表示为
$ {\delta }_{i}\left(v\right)=\underset{u\in {R}_{i}\left(v\right)}{\bar{\oplus}}\left({\delta }_{i}\left(u,v\right)\right),v\in {T}_{i} \text{,} $
$ {g}_{i}\left(v\right)={g}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left(v\right)\lus {\delta }_{i}\left(v\right),v\in {T}_{i} \;。$
在式(8)中,$ {\delta }_{i}\left(v\right) $表示第$ i $轮迭代计算中顶点$ v $的聚合值变化量,$ {\delta }_{i}(u,v) $表示第$ i $轮迭代计算中顶点$ u $对顶点$ v $的聚合值变化量的贡献,$ \bar{\oplus} $为修正聚合算子。在PageRank算法中,$ {\delta }_{i}\left(v\right) =\displaystyle\sum _{u\in {R}_{i}\left(v\right)}{\delta }_{i}\left(u,v\right) $。在式(9)中,$ \lus $为对历史聚合值进行修正的算子。对于PageRank算法,$ {g}_{i}\left(v\right) ={g}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left(v\right)+{\delta }_{i}\left(v\right) $。
接下来进入点计算阶段,只有集合$ {T}_{i} $中的顶点才需进行新的顶点状态值的计算和顶点状态值的更新,而对不属于$ {T}_{i} $的顶点,由于其顶点状态值未受更新边流影响而改变,故直接复用历史顶点状态值。该过程可以表示为
$ d_i\left(v\right)=\left\{\begin{aligned} & upt(d_{i-1}\left(v\right),\displaystyle\oint g_i\left(v\right)),\; \; v\in T_i\ , \\ & d_i^{\mathrm{o}\mathrm{l}\mathrm{d}}\left(v\right),\; \; v\notin T_i\; 。\end{aligned}\right. $
图1(b)给出了PageRank算法在基于修正的增量计算模式下的迭代计算过程示意图,图1(a)是被处理的流式图示例,图$ {G'} $由图$ G $插入一条边$ ({v}_{0},{v}_{1}) $得到。在第1轮迭代计算中,顶点$ {v}_{0} $被激活,触发其出射邻居顶点$ {v}_{1} $和$ {v}_{3} $来修正历史聚合值并计算顶点状态值。在第2轮迭代计算中,顶点$ {v}_{0} $,$ {v}_{1} $,$ {v}_{3} $被激活,分别触发它们的出射邻居顶点(顶点$ {v}_{0} $的出射邻居顶点为$ {v}_{1} $和$ {v}_{3} $,顶点$ {v}_{1} $没有出射邻居顶点,顶点$ {v}_{3} $的出射邻居顶点为$ {v}_{1} $和$ {v}_{4} $)来修正历史聚合值并计算顶点状态值。在第3轮迭代计算中,被激活的顶点为$ {v}_{0} $,$ {v}_{1} $,$ {v}_{3} $,$ {v}_{4} $,须要修正顶点状态值的顶点为$ {v}_{1} $,$ {v}_{3} $,$ {v}_{4} $。
基于重计算的增量计算模式[8]也是通过对历史计算结果进行存储和复用来进行增量计算,但与基于修正的增量计算模式不同,其不对历史计算结果进行修正,而是直接触发受更新影响而顶点状态值改变的顶点进行重新计算,其他顶点则直接复用历史计算结果。基于重计算的增量计算模式可以用式(11)表示。
$ (D_i,G_i)=f_{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}(D_i^{\mathrm{o}\mathrm{l}\mathrm{d}},G_i^{\mathrm{o}\mathrm{l}\mathrm{d}},D_{i-1})\text{ ,} $
其中映射$ {f}_{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $由采用了基于重计算的增量计算模式的特定图算法定义。
不论是基于修正还是基于重计算的增量计算模式,它们的目标都是对受更新影响而导致顶点状态值变化的顶点进行识别和计算,以得到正确的顶点状态值。因此,基于重计算的增量计算模式中第$ i $轮迭代计算须要参与重新计算的顶点构成的集合,即为基于修正的计算模式中第$ i $轮迭代计算须要修正顶点状态值的顶点构成的集合$ {T}_{i} $。在边计算阶段,$ {T}_{i} $中的顶点通过拉取方式访问其所有入射邻居的第$ i-1 $轮迭代计算的顶点状态值来计算聚合值。设基于重计算的增量计算模式在第$ i $轮迭代计算的活跃顶点集合为$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $,有
$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}={T}_{i} \;。$
边计算过程可以表示为
$ {g}_{i}\left(v\right)=\underset{u\in {N}_{\mathrm{i}\mathrm{n}}\left(v\right)}{\oplus}\left({d}_{i-1}\left(u\right)\right),v\in {T}_{i} \;。$
在点计算阶段,集合$ {T}_{i} $中的顶点计算新的顶点状态值并更新顶点状态值,而不属于集合$ {T}_{i} $的顶点,则直接复用历史顶点状态值。该计算过程与基于修正的增量计算模式相同,可以表示为式(10)。
图1(c)给出了PageRank算法在基于重计算的增量计算模式下的迭代计算过程示意图。在第1轮迭代计算中,顶点$ {v}_{1} $和$ {v}_{3} $被激活,它们分别通过访问其入射邻居顶点(顶点$ {v}_{1} $的入射邻居顶点为$ {v}_{0} $,$ {v}_{2} $,$ {v}_{3} $,顶点$ {v}_{3} $的入射邻居顶点为$ {v}_{0} $)重新计算聚合值和顶点状态值。在第2轮迭代计算中,顶点$ {v}_{1} $,$ {v}_{3} $,$ {v}_{4} $被激活,分别通过访问它们的入射邻居(顶点$ {v}_{4} $的入射邻居顶点为$ {v}_{2} $和$ {v}_{3} $)来重新计算聚合值和顶点状态值。第3轮迭代计算则与第2轮迭代计算的过程相同。
下面分别在边计算和点计算2个阶段从理论上对基于修正和基于重计算的增量计算模式进行对比分析。
1)边计算阶段
由式(7)~(9)可知,对于基于修正的增量计算模式,在第$ i $轮迭代计算的活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $中的顶点$ u $以推送方式精确触发其出射邻居顶点$ v $来修正历史聚合值$ {g}_{i}^{\mathrm{o}\mathrm{l}\mathrm{d}}\left(v\right) $。这意味在第$ i $轮迭代计算中,基于修正的增量计算模式对边的访问量为$ | \{ (u,v )\in {E'} | u\in {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}\} | $。而由式(12)(13)可知,对于基于重计算的增量计算模式,在第$ i $轮迭代计算的活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $(即集合$ {T}_{i} $)中的顶点$ v $以拉取方式访问所有的入射邻居顶点来重新计算聚合值$ {g}_{i}\left(v\right) $。这表明在第$ i $轮迭代计算中,基于重计算的增量计算模式对边的访问量等于集合$ {T}_{i} $中所有顶点的入射邻居数量的总和(即$ \displaystyle\sum _{v\in {T}_{i}}\left|{N}_{\mathrm{i}\mathrm{n}}\right(v\left)\right| $)。因此,基于重计算的增量计算模式相比基于修正的增量计算模式对边的访问量更多以及涉及更多的访存操作,带来更大的访存开销。以图1为例,在第1轮迭代计算中,对于基于修正的增量计算模式,活跃顶点$ {v}_{0} $只访问了边$ \left({v}_{0},{v}_{1}\right) $和$ ({v}_{0},{v}_{3}) $;而对于基于重计算的增量计算模式,活跃顶点$ {v}_{1} $访问了边$ ({v}_{0},{v}_{1}) $,$ ({v}_{2},{v}_{1}) $,$ \left({v}_{3},{v}_{1}\right) $,而活跃顶点$ {v}_{3} $则访问了边$ ({v}_{0},{v}_{3}) $。
此外,由于基于修正的增量计算模式采用了推送模式来访问出射邻居,故需要采用原子操作来解决数据竞争的问题;而基于重计算的增量计算模式采用了拉取模式来访问入射邻居,不会产生数据竞争,故不需要原子操作。由于原子操作需要一定的时间开销,所以当计算量相同时,基于修正的增量计算模式相比基于重计算的增量计算模式需要更多的计算时间。因此,基于修正和基于重计算的增量计算模式的性能可能在不同图数据集和图算法场景下呈现不同的性能优劣情况。
2)点计算阶段
从3.1节和3.2节的分析可知,基于修正和基于重计算的增量计算模式的目标均是为受更新影响而顶点状态值改变的顶点(即集合$ {T}_{i} $中的顶点)计算新的顶点状态值。由于受更新影响而改变顶点状态值的顶点是由图数据集、更新边流和图算法性质决定的,而与增量计算的模式无关,所以基于修正的和基于重计算的增量计算模式在点计算阶段需要进行顶点状态值计算的顶点数量是相等的。例如,在图1中,基于修正和基于重计算的增量计算模式在每一轮迭代中进行顶点状态值计算的顶点相同。因此,在点计算阶段,基于修正和基于重计算的增量计算模式的性能差异较小。
综合3.3节的分析,我们选择顶点数量、平均度数、更新边流大小和图算法类型这4个典型特征作为实验参数,分析不同参数设置情况下2种增量计算模式的性能差异。本文将代码实现的基于修正和基于重计算的增量计算模式分别称为IncRefine和IncRecpt模式。我们采用了PageRank[1],Label Propagation[34],BFS[15],SSSP[16]这4种典型的图算法,在RMAT[35]生成图数据集上进行对比实验,5.1节对详细的实验设置进行了介绍。
在RMAT24_16数据集上,我们设置更新边流的大小$ \left|{\Delta }G\right| $分别为10和107,测试了上述4种图算法在IncRefine和IncRecpt模式下每轮迭代计算的执行时间。图2(a)给出了PageRank算法的实验结果,从中可以看出,当$ \left|{\Delta }G\right|=10 $时,IncRefine模式的性能全过程优于IncRecpt模式;当$ \left|{\Delta }G\right|={10}^{7} $时,2种增量计算模式的性能接近。图2(b)给出了Label Propagation算法的实验结果,从中可以看出,当$ \left|{\Delta }G\right|=10 $时,在前3轮迭代计算中整体上IncRefine模式的性能更优,但在第4轮迭代计算以后IncRecpt模式的性能更优;当$ \left|{\Delta }G\right|={10}^{7} $时,在第1轮迭代计算中IncRefine模式的性能更优,但在之后的迭代计算中IncRecpt模式的性能更优。图2(c)给出了BFS算法的实验结果,从图中可以看出,当$ \left|{\Delta }G\right|=10 $时,在第2~5轮迭代计算中IncRefine模式的性能更优,在第1,6,7轮迭代计算中2种模式的性能接近;当$ \left|{\Delta }G\right|={10}^{7} $时,在第3轮迭代计算中IncRecpt模式的性能更优,但在其他轮迭代计算中IncRefine模式的性能更优。图2(d)给出了SSSP算法的实验结果,其表现出了和BFS算法相近的趋势。总体来说,不同图算法在迭代计算过程中的2种增量计算模式呈现出不同的性能优劣情况,这是因为2种增量计算模式采用的算子是由特定图算法定义的(例如聚合算子和顶点状态值计算算子)。而当更新边流大小$ \left|{\Delta }G\right| $变化时,2种增量计算模式的性能也呈现出差异,这是因为$ \left|{\Delta }G\right| $直接影响了每一轮迭代中需要计算顶点状态值的顶点数量$ \left|{T}_{i}\right| $,由3.3节的理论分析可知,这会导致2种增量计算模式的访存开销和计算开销发生变化,从而影响算法性能。
为了进一步探究图数据集的大小对实验结果的影响,我们在RMAT24_10,RMAT24_19,RMAT20_16,RMAT25_16这 4个数据集上,分别测试了4种图算法在2种增量计算模式下每轮迭代计算的执行时间,其中$ \left|{\Delta }G\right| $的大小设置为$ {10}^{3} $。限于篇幅,我们只展示了PageRank和BFS算法的实验结果。图2(e)(f)给出了PageRank算法在4个大小不同的图数据集上的执行结果。从图2(e)中可以看出,在RMAT24_10和RMAT24_19数据集上,IncRefine模式的性能整体上优于IncRecpt模式。从图2(f)中可以看出,在RMAT20_16数据集上,除了前2轮迭代计算以外,IncRecpt模式的性能优于IncRefine模式;在RMAT25_16数据集上,在前2轮迭代计算中IncRefine模式的性能更优,之后2种模式的性能则接近。图2(g)(h)给出了BFS算法的实验结果。从图2(g)中可以看出,对于RMAT24_10和RMAT24_19数据集,在迭代计算前期和后期IncRefine模式整体上性能更优,在第3轮迭代计算中IncRecpt模式的性能更优。从图2(h)中可以看出,在RMAT20_16和RMAT25_16数据集上,在迭代计算前期和后期IncRecpt模式的性能整体上更优,在迭代计算中期IncRefine模式的性能更优。综合来看,在不同的图数据集规模下,2种增量计算模式呈现出不同的性能优劣情况。当平均度数和$ \left|{\Delta }G\right| $相等时,顶点数量更多的图数据集带来了更长的图算法执行时间,这是因为需要计算顶点状态值的顶点数量$ \left|{T}_{i}\right| $增多,由3.3节的理论分析可知,这会间接导致2种增量计算模式呈现不同的性能优劣情况。而当图数据集的顶点数量和$ \left|{\Delta }G\right| $相等时,平均度数的增加很可能会导致在边计算阶段IncRecpt模式相比IncRefine模式的边访问量增加得更多,这也会导致2种增量计算模式呈现不同的性能优劣情况。
通过实验对比分析可以看出,随着迭代计算的进行,不同的顶点数量、平均度数、更新边流大小和图算法类型都会影响2种增量计算模式的性能。在迭代计算过程中较优的增量计算模式不是固定不变的。
本节提出并代码实现了混合增量计算模式(下文称为IncHybrid模式),首先给出在2种增量计算模式之间正确切换的算法,然后介绍基于随机森林分类器的切换机制。
我们通过在2种增量计算模式之间传递迭代计算所需的活跃顶点集合来保证切换的正确性,即由其中一种增量计算模式在第$ i $轮迭代计算中的活跃顶点集合求得另一种增量计算模式在第$ i+1 $轮迭代计算中的活跃顶点集合。
1)IncRefine模式切换到IncRecpt模式
由式(7)(12)可知,IncRefine模式在第$ i $轮迭代计算的活跃顶点集合 $ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $中所有顶点的出射邻居构成的集合即为IncRecpt模式在第$ i $轮迭代计算的活跃顶点集合 $ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $。因此,我们先通过活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $求出活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $,再根据活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $求出活跃顶点集合$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $。具体过程如算法1所示。首先并行地遍历活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $中的顶点并将其出射邻居顶点放入活跃顶点集合 $ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中(行①~⑤),活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中的顶点均被激活为下一轮迭代计算的活跃顶点(行⑥),之后并行地遍历活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中的顶点并将其出射邻居顶点放入活跃顶点集合$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中(行⑦~⑪)。
算法1. IncRefine模式切换到IncRecpt模式。
输入:IncRefine模式在第$ i $轮迭代计算的活跃点集$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $;
输出:IncRecpt模式在第$ i+1 $轮迭代计算的活跃点集$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $。
① parallel-for $ u\in {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $ do
② parallel-for $ v\in {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}\left(u\right) $ do
③  将顶点$ v $放入集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中;
④ end parallel-for
⑤ end parallel-for
⑥ $ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}\leftarrow {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $;
⑦ parallel-for $ u\in {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $ do
⑧ parallel-for $ v\in {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}\left(u\right) $ do
⑨  将顶点$ v $放入集合$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中;
⑩ end parallel-for
⑪ end parallel-for
下面以图1中PageRank算法在IncRefine模式下的第1轮迭代计算切换到IncRecpt模式下的第2轮迭代计算为例介绍该切换过程。在IncRefine模式下的第1轮迭代计算中(图1(b)),$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}=\left\{{v}_{0}\right\} $,将其输入算法1中,输出为$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}=\{{v}_{1},{v}_{3},{v}_{4}\} $(对应图1(c)第2轮迭代计算中的活跃顶点)。
2)IncRecpt模式切换到IncRefine模式
IncRecpt模式在第$ i $轮迭代计算的活跃顶点集合 $ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中的所有顶点均属于IncRefine模式在第$ i+1 $轮迭代计算的活跃顶点集合 $ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $。此外,在IncRefine模式中,受更新边流$ {\Delta }G $直接影响的顶点也要作为活跃顶点参与每轮迭代计算。具体过程如算法2所示。首先,活跃顶点集合$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $中的顶点均被激活为IncRefine模式在第$ i+1 $轮迭代计算的活跃顶点(行①),然后并行地遍历更新边流集合$ {\Delta }G $中的边并根据特定图算法定义的影响算子$af fect(\cdot ) $判断是否激活该边的源顶点和目的顶点(行②~⑨)。影响算子$ af fect(\cdot ) $负责判断顶点是否受更新边流$ {\Delta }G $直接影响。例如,在PageRank算法中,影响算子$af fect(\cdot ) $的功能为判断某个顶点的出度是否发生改变,若改变则输出$ \mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $,否则输出$ \mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e} $。
算法2. IncRecpt模式切换到IncRefine模式。
输入:IncRecpt模式在第$ i $轮迭代计算的活跃点集$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $;
输出:IncRefine模式在第$ i+1 $轮迭代计算的活跃点集$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $。
① $ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}\leftarrow {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $;
② parallel-for $ \left(u,v\right)\in {\Delta }G $ do
③ if $ af fect\left(u\right)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $ then
④  将顶点$ u $放入集合$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $中;
⑤ end if
⑥ if $ af fect\left(v\right)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $ then
⑦  将顶点$ v $放入集合$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $中;
⑧ end if
⑨ end parallel-for
下面以图1中PageRank算法在IncRecpt模式下的第2轮迭代计算切换到IncRefine模式下的第3轮迭代计算为例介绍该切换过程。在IncRecpt模式下的第2轮迭代计算中(图1(c)),$ {F}_{i}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}=\left\{{{v}_{1},{v}_{3},v}_{4}\right\} $,将其输入算法2中,输出为$ {F}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}=\{{{{v}_{0},v}_{1},{v}_{3},v}_{4}\} $(对应图1(b)第3轮迭代计算中的活跃顶点)。
本文采用随机森林分类器[36]预测2种增量计算模式的切换时机。随机森林分类器由多棵决策树构成,通过每棵决策树投票得出最终的预测结果,其具有较高的预测准确率和鲁棒性,且不容易出现过拟合问题。
预测2种增量计算模式的切换时机通常可以采用2种方式:1)在迭代计算之前对切换时机进行预测(在哪一轮迭代计算进行切换);2)在迭代计算过程中对切换时机进行预测(在每轮迭代计算之前预测是否切换)。第1种方式只需运行1次随机森林分类器,故切换开销小,但其无法利用迭代计算过程中产生的信息进行预测,而只能通过迭代计算前的输入信息和先验知识进行预测,故在未知分布的图数据集上可能表现出较差的泛化能力。第2种方式需要在每一轮迭代计算之前运行1次分类器,且需要收集迭代计算过程中产生的特定信息,故切换开销较大,但其能够利用最新产生的迭代计算信息辅助预测,相比第1种方式能够更灵活地适应未知分布的图数据集。
为了充分验证混合增量计算模型的有效性,本文在RMAT生成图和真实图2类图数据集上均进行了实验。由于RMAT图数据集的分布较为一致,因此我们采用上述第1种方式预测2种增量计算模式的切换时机,以实现较低的切换开销。而对于真实图数据集,为了能够适应真实场景中复杂的图数据特征,我们采用上述第2种方式灵活地预测是否在下一轮迭代计算进行切换。我们为RMAT生成图数据集和真实图数据集分别训练了2个随机森林分类器,下面对训练过程进行详细介绍。
1)RMAT生成图数据集分类器
我们将BFS,SSSP,PageRank,Label Propagation 这4种图算法分别编号为1,2,3,4,选择RMAT图数据集的规模、平均度数、更新边流大小和图算法编号4个参数作为特征数据。特征数据可以表示为四元组:
$ \left(S,{D}_{\mathrm{a}\mathrm{v}\mathrm{g}},\left|{\Delta }G\right|,{A}_{\mathrm{i}\mathrm{d}}\right)\text{,} $
其中$ S $表示图数据集的规模(顶点数量为$ {2}^{S} $),$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $表示图数据集的平均度数,$ {A}_{\mathrm{i}\mathrm{d}} $表示图算法的编号。
我们将IncRefine和IncRecpt这2种增量计算模式分别编号为0和1,为了降低预测的复杂度,我们最多进行2次切换。目标数据可以表示成三元组:
$ ({M}_{\mathrm{i}\mathrm{d}},{I}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}},{I}_{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}) \;。 $
其中$ {M}_{\mathrm{i}\mathrm{d}} $表示在第1轮迭代计算所采用的增量计算模式,$ {M}_{\mathrm{i}\mathrm{d}}=0 $表示采用IncRefine模式,$ {M}_{\mathrm{i}\mathrm{d}}=1 $表示采用IncRecpt模式;$ {I}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}} $表示从哪一轮迭代计算开始由$ {M}_{\mathrm{i}\mathrm{d}} $代表的模式切换到另一种模式(即第1次切换);$ {I}_{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}} $表示从哪一轮迭代计算开始切换回由$ {M}_{\mathrm{i}\mathrm{d}} $代表的模式(即第2次切换)。若$ {I}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}}=-1 $,则不进行切换,若$ {I}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}}\ne -1 $且$ {I}_{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}=-1 $,则进行1次切换,若$ {I}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}}\ne -1 $且$ {I}_{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}\ne -1 $,则进行2次切换。
经过测试,RMAT生成图数据集分类器的预测准确率为$ 93\% $,平均预测时间开销为$ {7\times 10}^{-5} $ s(在图算法总体执行时间中占比小于 1%)。
2)真实图数据集分类器
在迭代计算过程中,除了式(14)所采用的4个参数以外,我们可以另外收集每轮迭代计算的活跃顶点数量、活跃顶点的平均度数、所采用的增量计算模式种类以及图算法执行时间等作为特征数据,在下一轮迭代计算开始之前预测是否切换。收集活跃顶点的平均度数需要访问所有活跃顶点的度大小,该过程耗时较长,会较大地降低图算法的总体执行时间。因此,我们只额外增加每轮迭代计算的活跃顶点数量、所采用的增量计算模式种类以及图算法执行时间3个参数。假设图算法共进行了$ k $轮迭代计算,特征数据可以表示为七元组:
$ \left(n,{D}_{\mathrm{a}\mathrm{v}\mathrm{g}},\left|\Delta G\right|,{A}_{\mathrm{i}\mathrm{d}},{N}_{\mathrm{f}}^{i},{t}^{i},{M}_{\mathrm{i}\mathrm{d}}^{i}\right),i=\mathrm{0,1},… ,k-1 \;。$
其中$ {N}_{\mathrm{f}}^{i} $和$ {t}^{i} $分别表示第$ i $轮迭代计算的活跃顶点数量和图算法执行时间;$ {M}_{\mathrm{i}\mathrm{d}}^{i} $表示第$ i $轮迭代计算所采用的增量计算模式,$ {M}_{\mathrm{i}\mathrm{d}}^{i}=0 $表示采用了IncRefine模式,$ {M}_{\mathrm{i}\mathrm{d}}^{i}= 1 $表示采用了IncRecpt模式。需要注意的是,在第1轮迭代计算之前需要对第1轮迭代计算采用何种增量计算模式进行预测(即$ i=0 $时),我们规定$ {N}_{\mathrm{f}}^{0}= 0 $,$ {t}^{0}=0 $,$ {M}_{\mathrm{i}\mathrm{d}}^{0}=-1 $。
对于第1轮迭代计算之前的预测,我们设置目标数据为2种增量计算模式的图算法总体执行时间。而对于其他轮迭代计算之前的预测,我们设置目标数据为2种增量计算模式在每轮迭代计算的图算法执行时间。目标数据可以表示为二元组:
$ \left({{t}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}},t}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}\right),i=\mathrm{0,1},… ,k-1\text{,} $
其中当$ i=0 $时,$ {t}_{1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $和$ {t}_{1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $分别表示IncRefine和IncRecpt模式的图算法总体执行时间,而$ i \gt 0 $时,$ {t}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}} $和$ {t}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}} $分别表示IncRefine和IncRecpt模式在第$ i +1$轮迭代计算的图算法执行时间。
经过测试,真实图数据集分类器的预测准确率为$ 89\% $,每轮迭代计算的平均预测时间开销$ {t}_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}}=2\times {10}^{-4} $ s。由于图算法需要进行多次迭代计算,故累积的总体预测时间开销为毫秒级别,在图算法总体执行时间中的占比最高约为$ 10\% $。
在迭代计算过程中,当其中一种增量计算模式的性能总是比另一种增量计算模式的性能更优时,通过真实图数据集分类器进行预测不仅不会带来性能增益,反而会额外增加预测时间开销。因此,我们设定阈值$ \alpha $(默认为0.5),对于第1轮迭代计算之前的预测,当
$ \dfrac{\left|{t}_{1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}-{t}_{1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}\right|}{\mathrm{m}\mathrm{i}\mathrm{n}({t}_{1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}},{t}_{1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}})} \gt \alpha $
时,在整个迭代计算过程中以性能更优的增量计算模式执行图算法,而不使用分类器进行预测。另外,当2种增量计算模式在第$ i +1$轮迭代计算($ i \gt 0 $)的图算法执行时间差不大于预测时间开销时,切换带来的收益会小于其带来的开销。因此,我们设定迭代计算过程中的切换条件为
$ \left|{t}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}}-{t}_{i+1}^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{p}\mathrm{t}}\right| \gt {t}_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}},\;\;i=\mathrm{1,2},… ,k-1 \;。$
当式(19)成立时,才从性能较差的增量计算模式切换到性能较优的增量计算模式。
本节首先介绍实验设置,然后分别在RMAT生成图数据集和真实图数据集上对IncHybrid模式的性能进行评估。
1)实验平台
本文采用带有 Intel® Xeon® Platinum 8269CY 处理器(26核52线程,主频2.50 GHz)和256 GB DDR4内存的计算机,该机器运行64位的CentOS 7 操作系统,编译器采用了支持CilkPlus[37]并行编程框架的GCC 5.5.0(使用-O3优化)。
2)工作负载
本文采用了PageRank[1],Label Propagation[34],BFS[15],SSSP[16]这4种典型的图算法。我们设置PageRank算法的阻尼系数$ d=0.85 $,设置PageRank和Label Propagation算法的更新阈值$ \epsilon={10}^{-5} $。此外,PageRank和Label Propagation算法的迭代计算轮数上限被设置为20,而BFS和SSSP算法则迭代计算到收敛为止。
3)图数据集
本文采用RMAT[35]生成图数据集和真实图数据集。RMAT数据集是Graph500[38]榜单采用的官方数据集,其模拟了真实图数据的特征。我们设置参数$ a=0.57 $,$ b=c=0.19 $,生成了9个不同顶点规模和平均度数的RMAT有向图数据集。对于真实图数据集,采用了源于斯坦福大学SNAP项目的5个图数据集,如表1所示,com-LiveJournal (LJ)[39],com-Orkut (OR)[39],soc-Pokec (PK)[40]为社交网络图数据集,而roadNet-CA (CA)[41]和roadNet-TX (TX)[41]为道路网络图数据集。我们参考文献[6-7]的工作对流式图进行模拟,随机抽取图数据集50%的边构造基础图,然后从基础图中随机选择删除的边,而从剩下50%的边中随机选择插入的边,删除的边和插入的边构成更新边流$ {\Delta }G $,本文固定更新边流中删除边和插入边的比例为1∶1。
1)性能评估
图3给出了当$ \left|{\Delta }G\right|=1\;000 $时,4种图算法在RMAT_$ S $_16($ S\in \left\{\mathrm{20,21,22,23,24,25}\right\} $)这6个数据集上IncHybrid,IncRefine,IncRecpt模式下相比Tradition模式的加速比。BFS,SSSP,PageRank,Label Propagation 这4种图算法在IncHybrid模式下相比Tradition模式平均实现了$ 2.56 $、$ 2.40 $、$ 1.62 $和$ 1.30 $的加速比。从图3(a)(b)中可以看出,对于BFS和SSSP算法,IncRefine模式相比IncRecpt模式具有更优的整体性能,而它们相比Tradition模式都具有一定的提升,通过切换,IncHybrid模式成功达到了与IncRefine模式接近的性能。从图3(c)(d)中可以看出,PageRank和Label Propagation算法在IncRefine模式和IncRecpt模式下不同顶点规模的数据集上呈现的性能优劣不同。例如,当顶点数据规模不超过23时,Label Propagation算法在IncRefine模式下具有更优的性能,但当顶点规模为24和25时IncRecpt模式具有更优的性能。从中可以看出,在2种增量计算模式中IncHybrid模式成功达到了最佳的性能,这表明切换机制能够有效地采用性能更优的增量计算模式。
图4给出了当$ \left|{\Delta }G\right|=1\;000 $时,4种图算法在RMAT_$ 24 $_$ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}} $($ {D}_{\mathrm{a}\mathrm{v}\mathrm{g}}\in \left\{\mathrm{10,13,16,19}\right\} $)这4个数据集上分别采用IncHybrid,IncRefine,IncRecpt,Tradition模式的执行时间。BFS,SSSP,PageRank,Label Propagation算法在IncHybrid模式下相比Tradition模式实现了平均$ 2.43 $、$ 2.27 $、$ 1.22 $和$ 1.54 $的加速比。从图4中可以看出,当平均度数变化时,IncHybrid模式的性能与IncRefine和IncRecpt这2种模式中性能更优的那个的性能接近,这表明IncHybrid模式能够有效适应不同平均度数的数据集。图5给出了在RMAT_$ 25 $_$ 16 $数据集上,当更新边流大小$ \left|{\Delta }G\right| $变化时,BFS和PageRank算法在IncHybrid,IncRefine,IncRecpt模式下的执行时间。从图5中可以看出,当$ \left|{\Delta }G\right| $增大时,2种算法在3种增量计算模式下的执行时间均有所增加,这是因为受更新边流影响需要参与计算的顶点数量变多了,而IncHybrid模式仍然与IncRefine和IncRecpt这2种模式中性能更优的那个的性能接近,这表明其能够有效地适应不同的更新边流大小。
2)切换效果分析
图6给出了当$ \left|{\Delta }G\right|=10 $时,4种图算法在RMAT_25_16数据集上分别采用IncHybrid,IncRefine,IncRecpt模式的每轮迭代计算时间,实验结果表明IncHybrid模式能够有效进行切换并取得最优性能。
对于BFS算法,随机森林分类器的预测值为 $ (\mathrm{1,2},6) $,IncHybrid模式在第1轮迭代计算采用IncRecpt模式,然后在第2轮迭代计算切换到IncRefine模式,最后在第6轮迭代计算切换回IncRecpt模式。从图6(a)中可以看出,IncHybrid模式在每轮迭代计算中取得了较优的性能。最终BFS算法在IncHybrid模式下取得了$ 0.20 $ s的执行时间,而在IncRefine和IncRecpt模式分别取得了$ 0.21 $ s和$ 0.30 $ s的执行时间。
对于SSSP算法,随机森林分类器的预测值为$ (\mathrm{1,2},7) $,IncHybrid模式在第1轮迭代计算采用IncRecpt模式, 随后在第2轮迭代计算切换到IncRefine模式,最后在第7轮迭代计算切换回IncRecpt模式。从图6(b)中可以看出,IncHybrid模式成功切换到指定的模式并获得了最优的整体性能。SSSP算法在IncHybrid模式下的执行时间为$ 0.24 $ s,而在IncRefine和IncRecpt模式下的执行时间分别为$ 0.26 $ s和$ 0.46 $ s。
对于PageRank算法,随机森林分类器的预测值为$ (\mathrm{1,2},4) $,IncHybrid模式在第1轮迭代计算采用了IncRecpt模式,接着在第2轮迭代计算切换到IncRefine模式,之后在第4轮迭代计算切换回IncRecpt模式,如图6(c)所示。PageRank算法在IncHybrid模式下取得了$ 18.36 $ s的执行时间,而在IncRefine和IncRecpt模式下分别取得了$ 18.59 $ s和$ 18.81 $ s的执行时间。
对于Label Propagation算法,随机森林分类器的预测值为$ (\mathrm{0,4},-1) $,IncHybrid模式在第1轮迭代计算采用IncRefine模式,然后在第4轮迭代计算切换到IncRecpt模式,并在之后的迭代计算中继续采用IncRecpt模式,如图6(d)所示。最终Label Propagation算法在IncHybrid模式下的执行时间为$ 24.05 $ s,而在IncRefine 和IncRecpt模式下的执行时间分别为$ 28.87 $ s和$ 24.43 $ s。
3)与其他系统的比较
我们将IncHybrid模式和先进的流式图处理系统DZIG[19]进行了比较,DZIG系统采用了基于修正的增量计算模式,并同样使用基于BSP的以顶点为中心的迭代计算模型。由于DZIG系统的开源代码中未提供BFS和SSSP算法,所以我们在DZIG系统中实现了该2种算法。
表2给出了当更新边流大小$ \left|{\Delta }G\right|=1\;000 $时,在RMAT_$ S $_16($ S\in \left\{\mathrm{21,22,23,24}\right\} $)这4个数据集上,PageRank,Label Propagation,BFS,SSSP 这4种图算法在IncHybrid模式下以及采用DZIG系统的执行时间。总体上,IncHybrid模式相比DZIG系统实现了平均$ 1.25 $的加速比。从表2中可以看出,IncHybrid模式在大多数情况下的性能优于DZIG系统,其主要原因在于IncHybrid模式在迭代计算过程中会准确切换到IncRefine和IncRecpt模式中性能更优的模式。其中在RMAT_21_16数据集上,PageRank算法在IncHybrid模式下相比DZIG系统达到了1.92的加速比,这是因为IncHybrid模式在第1轮迭代计算中采用了IncRefine模式,而从第2轮迭代计算开始切换到了性能更优的IncRecpt模式。在某些情况下IncHybrid模式与DZIG系统的性能接近(例如 Label Propagation算法在RMAT_21_16,RMAT_22_16,RMAT_23_16这3个数据集上),这是因为IncHybrid模式从第1轮迭代计算开始只采用了IncRefine模式而没有进行切换。
图7给出了当$ \left|{\Delta }G\right|=1\;000 $时,BFS和SSSP算法在5个真实图数据集上分别采用IncHybrid,IncRefine,IncRecpt模式相比Tradition模式的加速比(我们省略了PageRank和Label Propagation算法,因为它们表现出与图7相似的结果)。
对于BFS算法,IncHybrid,IncRefine,IncRecpt模式相比Tradition模式的加速比分别为$ 4.10 $、$ 2.65 $和$ 3.55 $。对于SSSP算法,IncHybrid,IncRefine,IncRecpt模式相比Tradition模式的加速比分别为$ 3.46 $、$ 2.67 $和$ 3.45 $。我们发现当IncRefine和IncRecpt模式的性能较为接近时,IncHybrid模式能够有效地在迭代计算过程中选择并切换到性能更优的模式(例如图7(a)的OR数据集),从而获得更短的算法执行时间。从图7中可以看出,BFS算法在LJ数据集上以及SSSP算法在LJ和TX数据集上,IncRecpt模式的性能全过程优于IncRefine模式,通过在迭代计算之前比较预测出的2种增量计算模式的图算法总体执行时间(计算见式(18)),IncHybrid模式避免了不必要的预测时间开销,从而达到与IncRecpt模式相近的性能。
本文将增量计算归纳为基于修正的增量计算模式和基于重计算的增量计算模式,在对二者进行理论和实验分析的基础上,提出了混合增量计算模式,实现了在2种增量计算模式之间正确且有效地切换。本文提出的基于混合增量计算模式的流式图并行处理,在不同规模数据集、不同图算法以及不同更新边流大小下有效地实现了切换,相比先进的流式图处理系统DZIG实现了平均$ 1.25 $倍的性能提升。未来我们将探索采用其他预测模型进行优化,以更好地提升流式图处理的性能。
作者贡献声明:申玥负责方案整体设计、代码和论文的撰写;张婕、张园、曹华伟负责提出部分实验思路并修改论文;安学军、叶笑春提出指导意见。

参考文献 引证文献
排序方式:
1
Berkhin P. A survey on PageRank computing[J]. Internet Mathematics, 2005, 2(1): 73−120
2
Afarin M, Gao Chao, Rahman S, et al. CommonGraph: Graph analytics on evolving data[C]//Proc of the 28th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2023: 133−145
3
Zhang Yu, Liang Yuxuan, Zhao Jin, et al. Egraph: Efficient concurrent GPU-based dynamic graph processing[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(6): 5823−5836
4
Han Wentao, Miao Youshan, Li Kaiwei, et al. Chronos: A graph engine for temporal graph analysis[C]//Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 1−14
5
Miao Youshan, Han Wentao, Li Kaiwei, et al. Immortalgraph: A system for storage and analysis of temporal graphs[J]. ACM Transactions on Storage, 2015, 11(3): 1−34
6
Vora K, Gupta R, Xu Guoqing. KickStarter: Fast and accurate computations on streaming graphs via trimmed approximations[C]//Proc of the 22nd Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2017: 237−251
7
Mariappan M, Vora K. GraphBolt: Dependency-driven synchronous processing of streaming Graphs[C]//Proc of the 14th EuroSys Conf 2019. New York: ACM, 2019: 1−16
8
Iyer A P, Pu Qifan, Patel K, et al. TEGRA: Efficient ad-hoc analytics on evolving graphs[C]//Proc of the 18th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 337−355
9
Dhankhad S, Mohammed E, Far B. Supervised machine learning algorithms for credit card fraudulent transaction detection: A comparative study[C]//Proc of the 19th IEEE Int Conf on Information Reuse and Integration (IRI). Piscataway, NJ: IEEE, 2018: 122−125
10
Gupta P, Satuluri V, Grewal A, et al. Real-time Twitter recommendation: Online motif detection in large dynamic graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(13): 1379−1380
11
Kwak H, Lee C, Park H, et al. What is Twitter, a social network or a news media?[C]//Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 591−600
12
Besta M, Fischer M, Kalavri V, et al. Practice of streaming processing of dynamic graphs: Concepts, models, and systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 34(6): 1860−1876
13
张园, 曹华伟, 张婕, 等. 面向多核CPU与GPU平台的图处理系统关键技术综述[J]. 计算机研究与发展, 2024, 61(6): 1401−1428
Zhang Yuan, Cao Huawei, Zhang Jie, et al. Survey on key technologies of graph processing systems based on multi-core CPU and GPU platforms[J]. Journal of Computer Research and Development, 2024, 61(6): 1401−1428 (in Chinese)
14
Fan Wenfei, Tian Chao. Incremental graph computations: Doable and undoable[J]. ACM Transactions on Database Systems, 2022, 47(2): 1−44
15
Beamer S, Asanović K, Patterson D. Direction optimizing breadth first search[J]. Scientific Programming, 2013, 21(3/4): 137−148
16
Chakaravarthy V T, Checconi F, Murali P, et al. Scalable single source shortest path algorithms for massively parallel systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 28(7): 2031−2045
17
Feng Guanyu, Ma Zixuan, Li Daixuan, et al. RisGraph: A real-time streaming system for evolving graphs to support sub-millisecond per update analysis at millions Ops/s[C]//Proc of the 48th Int Conf on Management of Data. New York: ACM, 2021: 513−527
18
Jiang Xiaolin, Xu Chengshuo, Yin Xizhe, et al. Tripoline: Generalized incremental graph processing via graph triangle inequality[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 17−32
19
Mariappan M, Che J, Vora K. DZIG: Sparsity-aware incremental processing of streaming graphs[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 83−98
20
Gong Shufeng, Tian Chao, Yin Qiang, et al. Ingress: An automated incremental graph processing system[J]. The VLDB Journal, 2024, 33(3): 781−806
21
Murray D G, McSherry F, Isaacs R, et al. Naiad: A timely dataflow system[C]//Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 439−455
22
Carbone P, Katsifodimos A, Ewen S, et al. Apache Flink: Stream and batch processing in a single engine[J]. The Bulletin of the Technical Committee on Data Engineering, 2015, 38(4): 28−38
23
Shi Xiaogang, Cui Bin, Shao Yingxia, et al. Tornado: A system for real-time iterative analysis over evolving data[C]//Proc of the 43rd Int Conf on Management of Data. New York: ACM, 2016: 417−430
24
Toshniwal A, Taneja S, Shukla A, et al. Storm@ Twitter[C]//Proc of the 41st Int Conf on Management of Data. New York: ACM, 2014: 147−156
25
Chen Dan, Gui Chuangyi, Zhang Yi, et al. GraphFly: Efficient asynchronous streaming graphs processing via dependency-flow[C]//Proc of the 35th Int Conf for High Performance Computing, Networking, Storage and Analysis. Piscataway, NJ: IEEE, 2022: 1−14
26
Jiang Zihan, Mao Fubing, Guo Yapu, et al. ACGraph: Accelerating streaming graph processing via dependence hierarchy[C]//Proc of the 60th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2023: 1−6
27
Valiant L G. A bridging model for parallel computation[J]. Communications of the ACM, 1990, 33(8): 103−111
28
Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C]//Proc of the 37th Int Conf on Management of Data. New York: ACM, 2010: 135−146
29
Shun Julian, Blelloch G E. Ligra: A lightweight graph processing framework for shared memory[C]//Proc of the 18th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2013: 135−146
30
Kyrola A, Blelloch G, Guestrin C. GraphChi: Large-scale graph computation on just a PC[C]//Proc of the 10th USENIX Conf on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 31−46
31
Zhu Xiaowei, Han Wentao, Chen Wenguang. GridGraph: Large scale graph processing on a single machine using 2-level hierarchical partitioning[C]//Proc of the 21st USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 375−386
32
Low Y, Gonzalez J, Kyrola A, et al. GraphLab: A new framework for parallel machine learning[C]//Proc of the 26th Conf on Uncertainty in Artificial Intelligence. Arlington, Virginia: AUAI, 2010: 340−349
33
Ediger D, McColl R, Riedy J, et al. Stinger: High performance data structure for streaming graphs[C]//Proc of the 16th IEEE Conf on High Performance Extreme Computing. Piscataway, NJ: IEEE, 2012: 1−5
34
Iscen A, Tolias G, Avrithis Y, et al. Label propagation for deep semi-supervised learning[C]//Proc of the 32nd IEEE/CVF Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2019: 1−10
35
Chakrabarti D, Zhan Yiping, Faloutsos C. RMAT: A recursive model for graph mining[C]//Proc of the 4th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2004: 442−446
36
Breiman L. Random forests[J]. Machine Learning, 2001, 45: 5−32
37
Leiserson C E. The Cilk++ concurrency platform[C]//Proc of the 46th Annual Design Automation Conf. Piscataway, NJ: IEEE, 2009: 522−527
38
Bader D A, Berry J, Kahan S, et al. Graph500[EB/OL]. 2010[2025-05-05]. http://www.graph500.org
39
Yang Jaewon, Leskovec J. Defining and evaluating network communities based on ground-truth[C]//Proc of the 18th ACM SIGKDD Workshop on Mining Data Semantics. New York: ACM, 2012: 1−8
40
Takac L, Zabovsky M. Data analysis in public social networks[C/OL]//Proc of the Int Scientific Conf and Int Workshop Present Day Trends of Innovations. 2012[2025-05-05]. https://snap.stanford.edu/data/soc-pokec.pdf
41
Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1): 29−123
2026年第63卷第3期
215
94
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202550151
  • 接收时间:2025-03-01
  • 首发时间:2026-11-06
  • 出版时间:2026-03-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2025-03-01
  • 修回日期:2025-09-08
  • 录用日期:2025-10-11
基金
作者信息
    1处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190
    2中国科学院大学 北京 100049
    3中关村实验室 北京 100094

通讯作者:

参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550151
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏