Article(id=1327013332390883909, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327013054811845282, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202330386, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1684771200000, receivedDateStr=2023-05-23, revisedDate=1737648000000, revisedDateStr=2025-01-24, acceptedDate=1740931200000, acceptedDateStr=2025-03-03, onlineDate=1794314233156, onlineDateStr=2026-11-10, pubDate=1751299200000, pubDateStr=2025-07-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794314233156, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794314233156, creator=13701087609, updateTime=1794314233156, updator=13701087609, issue=Issue{id=1327013054811845282, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='7', pageStart='1595', pageEnd='1832', issueExtLink='null', onlineDate='null', pubDate='1751299200000', pubDateStr='2025-07-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794314166977, creator='13701087609', updateTime=1794376853183, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275980453950013, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327013054811845282, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275980453950014, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327013054811845282, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=1805, endPage=1815, ext={EN=ArticleExt(id=1327013333477208647, articleId=1327013332390883909, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=A Distributed Buffered Streaming Graph Partitioning Algorithm, columnId=1325493593498059289, journalTitle=Journal of Computer Research and Development, columnName=High Performance Computing, runingTitle=null, highlight=null, articleAbstract=

Graph partitioning is a key technique for parallel processing of big graphs. Existing graph partitioning algorithms struggle to balance partition quality and efficiency. Offline partitioning algorithms tend to achieve high partition quality but are time-consuming, while online (or streaming) partitioning algorithms are relatively efficient but suffer from suboptimal partition quality. To address the above problem, we propose a distributed streaming partitioning algorithm with a buffering mechanism in this paper. The algorithm utilizes a multi-loader and multi-partitioner architecture, where multiple loaders read graph data in parallel to improve loading efficiency. Each partitioner maintains a buffer to store graph vertices received from the corresponding loader and sorts them in descending order based on vertex degree, providing better decision-making data for partitioning. Four streaming heuristic rules are pre-configured in the partitioners, which perform parallel partitioning on vertices in the buffer with different goals in mind. A reflow mechanism is employed to fine-tune the partitioning results and improve quality. Experimental results in a distributed system environment show that the proposed algorithm improves partition quality (edge-cut ratio) by more than 18.8% compared with the best existing online partitioning algorithm. Additionally, it reduces the proportion of graph data loading time in the total partitioning time from an average of 30.8% in a single-loader single-partitioner architecture to an average of 20.1%.

, authors=Huikang Shi1, Zesheng Wang2, Kekun Hu3, Gang Dong3, Youjian Zhao1, *, authorsList=Huikang Shi, Zesheng Wang, Kekun Hu, Gang Dong, Youjian Zhao, authorCompany=null, correspAuthors=Youjian Zhao, authorNote=

born in 1975. PhD. His main research interest includes electronic and information

born in 1987. PhD, senior engineer. His main research interests include cloud computing, and information technology service

born in 1987. PhD, senior engineer. Member of CCF. His main research interests include graph processing and graph deep learning

born in 1979. PhD, senior engineer. Member of CCF. His main research interests includes FPGA design, architecture and applications

born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 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=1327013335784075872, articleId=1327013332390883909, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=一种带缓冲区的分布式流式图划分算法, columnId=1325493595259666971, journalTitle=计算机研究与发展, columnName=高性能计算, runingTitle=null, highlight=null, articleAbstract=

图划分是大图并行处理关键技术之一. 现有图划分算法存在划分质量和效率难以平衡的问题,主要体现在离线划分算法划分质量高但耗时长;在线(也称流式)划分算法相对高效但划分质量不理想. 为此,提出一种带缓冲区的分布式流式划分算法. 该算法采用多加载器-多划分器架构,多个加载器并行读取图数据,提高图数据加载效率;每个划分器维护一个缓冲区,缓存相应加载器发来的图顶点,并按顶点度数高低排序,为划分器提供更多决策依据. 划分器预置有4条流式启发式规则,围绕不同目标,对缓冲区中的顶点实施并行划分,并借助重流机制微调划分结果,改进划分质量. 分布式系统环境下的划分质量与性能实验表明:提出算法的划分质量(割边比)比当前最好的在线划分算法改善超过18.8个百分点,并将图数据加载时间在划分总时间的占比,从单划分器-单加载器架构流式划分算法的平均30.8%缩减至平均20.1%.

, authors=史惠康1, 王泽胜2, 胡克坤3, 董刚3, 赵有健1, *, authorsList=史惠康, 王泽胜, 胡克坤, 董刚, 赵有健, authorCompany=null, correspAuthors=赵有健, authorNote=

1975年生. 博士. 主要研究方向为电子与信息

1987年生. 博士,高级工程师. 主要研究方向为云计算、信息技术服务

1987年生. 博士,高级工程师. CCF会员. 主要研究方向为图计算、图深度学习

1979年生. 博士,高级工程师. CCF会员. 主要研究方向为FPGA芯片架构设计及其应用

1969年生. 博士,教授,博士生导师. 主要研究方向为高速互联网体系结构、交换与路由、高速网络设备

, correspAuthorsNote=
赵有健()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=ngB+EH5fYdeQaK2mLbR5TQ==, magXml=EfUjQJrE3r/wb7dgfIj+6Q==, pdfUrl=null, pdf=CCJCgQWDFIB2JgYKlgUpuQ==, pdfFileSize=1453286, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=o+FBfbfu+1cLxxenduq4rg==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=sSZuF3Bg8u8pmPhX+ts4Cg==, mapNumber=null, fund=null)}, authors=[Author(id=1327013336346112619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=shk@pku.org.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327013336463553133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336346112619, language=EN, stringName=Huikang Shi, firstName=Huikang, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084, bio={"content":"

born in 1975. PhD. His main research interest includes electronic and information

"}, bioImg=null, bioContent=

born in 1975. PhD. His main research interest includes electronic and information

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013336530661998, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336346112619, 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清华大学计算机科学与技术系 北京 100084, bio={"img":"4tVEfVspwTRRYbFHfjcrdg==","content":"

1975年生. 博士. 主要研究方向为电子与信息

"}, bioImg=4tVEfVspwTRRYbFHfjcrdg==, bioContent=

1975年生. 博士. 主要研究方向为电子与信息

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336006373985, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=1, ext=[AuthorCompanyExt(id=1327013336014762594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1327013336023151203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1清华大学计算机科学与技术系 北京 100084)])]), Author(id=1327013336698434160, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=1327013336773931634, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336698434160, language=EN, stringName=Zesheng Wang, firstName=Zesheng, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2China Electronics Standardization Institute, Beijing 100007, bio={"content":"

born in 1987. PhD, senior engineer. His main research interests include cloud computing, and information technology service

"}, bioImg=null, bioContent=

born in 1987. PhD, senior engineer. His main research interests include cloud computing, and information technology service

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013336874594931, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336698434160, language=CN, stringName=王泽胜, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2中国电子技术标准化研究院 北京 100007, bio={"img":"i//5m1ZBfvNqBlIC1e8riA==","content":"

1987年生. 博士,高级工程师. 主要研究方向为云计算、信息技术服务

"}, bioImg=i//5m1ZBfvNqBlIC1e8riA==, bioContent=

1987年生. 博士,高级工程师. 主要研究方向为云计算、信息技术服务

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336111231588, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=2, ext=[AuthorCompanyExt(id=1327013336140591717, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336111231588, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2China Electronics Standardization Institute, Beijing 100007), AuthorCompanyExt(id=1327013336153174630, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336111231588, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国电子技术标准化研究院 北京 100007)])]), Author(id=1327013336945898101, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, orderNo=2, 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=1327013337025589879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336945898101, language=EN, stringName=Kekun Hu, firstName=Kekun, middleName=null, lastName=Hu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3IEIT SYSTEMS Co., Ltd., Jinan 250101, bio={"content":"

born in 1987. PhD, senior engineer. Member of CCF. His main research interests include graph processing and graph deep learning

"}, bioImg=null, bioContent=

born in 1987. PhD, senior engineer. Member of CCF. His main research interests include graph processing and graph deep learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013337147224696, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336945898101, language=CN, stringName=胡克坤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3浪潮电子信息产业股份有限公司 济南 250101, bio={"img":"tlPRuliuf1qCF0Q5Z4QXig==","content":"

1987年生. 博士,高级工程师. CCF会员. 主要研究方向为图计算、图深度学习

"}, bioImg=tlPRuliuf1qCF0Q5Z4QXig==, bioContent=

1987年生. 博士,高级工程师. CCF会员. 主要研究方向为图计算、图深度学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336232866407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=3, ext=[AuthorCompanyExt(id=1327013336249643624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3IEIT SYSTEMS Co., Ltd., Jinan 250101), AuthorCompanyExt(id=1327013336266420841, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3浪潮电子信息产业股份有限公司 济南 250101)])]), Author(id=1327013337226916474, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=1327013337327579772, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337226916474, language=EN, stringName=Gang Dong, firstName=Gang, middleName=null, lastName=Dong, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3IEIT SYSTEMS Co., Ltd., Jinan 250101, bio={"content":"

born in 1979. PhD, senior engineer. Member of CCF. His main research interests includes FPGA design, architecture and applications

"}, bioImg=null, bioContent=

born in 1979. PhD, senior engineer. Member of CCF. His main research interests includes FPGA design, architecture and applications

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013337398882941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337226916474, language=CN, stringName=董刚, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3浪潮电子信息产业股份有限公司 济南 250101, bio={"img":"JbPtjMW4hPxLJ7N6seUrXw==","content":"

1979年生. 博士,高级工程师. CCF会员. 主要研究方向为FPGA芯片架构设计及其应用

"}, bioImg=JbPtjMW4hPxLJ7N6seUrXw==, bioContent=

1979年生. 博士,高级工程师. CCF会员. 主要研究方向为FPGA芯片架构设计及其应用

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336232866407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=3, ext=[AuthorCompanyExt(id=1327013336249643624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3IEIT SYSTEMS Co., Ltd., Jinan 250101), AuthorCompanyExt(id=1327013336266420841, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3浪潮电子信息产业股份有限公司 济南 250101)])]), Author(id=1327013337470186111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zhaoyoujian@tsinghua.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327013337545683585, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337470186111, language=EN, stringName=Youjian Zhao, firstName=Youjian, middleName=null, lastName=Zhao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084, bio={"content":"

born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

"}, bioImg=null, bioContent=

born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013337616986754, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337470186111, 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清华大学计算机科学与技术系 北京 100084, bio={"img":"scJ7dbmy7vjGqggAjH0hdA==","content":"

1969年生. 博士,教授,博士生导师. 主要研究方向为高速互联网体系结构、交换与路由、高速网络设备

"}, bioImg=scJ7dbmy7vjGqggAjH0hdA==, bioContent=

1969年生. 博士,教授,博士生导师. 主要研究方向为高速互联网体系结构、交换与路由、高速网络设备

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336006373985, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=1, ext=[AuthorCompanyExt(id=1327013336014762594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1327013336023151203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1清华大学计算机科学与技术系 北京 100084)])])], keywords=[Keyword(id=1327013337730232964, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, orderNo=1, keyword=big graph), Keyword(id=1327013337793147525, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, orderNo=2, keyword=streaming partitioning), Keyword(id=1327013337864450694, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, orderNo=3, keyword=distributed), Keyword(id=1327013337956725383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, orderNo=4, keyword=buffering), Keyword(id=1327013338028028552, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, orderNo=5, keyword=restreaming), Keyword(id=1327013338116108937, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, orderNo=1, keyword=大图), Keyword(id=1327013338187412106, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, orderNo=2, keyword=流式划分), Keyword(id=1327013338258715275, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, orderNo=3, keyword=分布式), Keyword(id=1327013338334212748, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, orderNo=4, keyword=缓冲), Keyword(id=1327013338401321613, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, orderNo=5, keyword=重流)], refs=[Reference(id=1327013341270225580, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Sakr S, Boifati A, Voigt H, et al. The future is big graphs: A community view on graph processing systems[J]. Communications of the ACM, 2021, 64(9): 62−71, articleTitle=null, refAbstract=null), Reference(id=1327013341362500269, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=杜玉洁,王志刚,王宁,等. 分布式多维大图迭代计算性能优化方法[J]. 计算机研究与发展,2023,60(3):654−675, articleTitle=null, refAbstract=null), Reference(id=1327013341442192046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Du Yujie, Wang Zhigang, Wang Ning, et al. Optimization methods for distributed iterative computing performance over multi-dimensional large graph[J]. Journal of Computer Research and Development, 2023, 60(3): 654−675 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327013341505106607, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Fan Wenfei. Big graphs: Challenges and opportunities [C]// Proc of the 48th Int Conf on Very Large Data Bases. New York: ACM, 2022: 3782−3797, articleTitle=null, refAbstract=null), Reference(id=1327013341563826864, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhai Xiaomeng, Zhang Hong, Huang Xu, et al. Graph partitioning strategies: One size does not fit all[J]. The Journal of Supercomputing, 2022, 78(17): 19272−19295, articleTitle=null, refAbstract=null), Reference(id=1327013341622547121, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Dhillon I. Co-clustering documents and words using bipartite spectral graph partitioning [C]//Proc of the 7th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2001: 269−274, articleTitle=null, refAbstract=null), Reference(id=1327013341693850290, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Karypis G, Kumar V. Multilevel graph partitioning schemes [C]// Proc of the 1995 Int Conf on Parallel Processing. Piscataway, NJ: IEEE, 1995: 113−122, articleTitle=null, refAbstract=null), Reference(id=1327013341773542067, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Jafari N, Selvitopi O, Aykanat C. Fast shared-memory streaming multilevel graph partitioning[J]. Journal of Parallel and Distributed Computing, 2021, 147(1): 140−151, articleTitle=null, refAbstract=null), Reference(id=1327013341832262324, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Ji Shengwei, Bu Chenyang, Li Lei, et al. Local graph edge partitioning[J]. ACM Transactions on Intelligent Systems and Technology, 2021, 12(5): 1−25, articleTitle=null, refAbstract=null), Reference(id=1327013341903565493, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Karypis G, Kumar V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distributed Computing, 1998, 48(1): 96−129, articleTitle=null, refAbstract=null), Reference(id=1327013341979062966, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Stanton I, Kliot G. Streaming graph partitioning for large distributed graphs [C]// Proc of the 18th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1222−1230, articleTitle=null, refAbstract=null), Reference(id=1327013342037783223, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Nishimura J, Ugander J. Restreaming graph partitioning: Simple versatile algorithms for advanced balancing [C]//Proc of the 19th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 1106−1114, articleTitle=null, refAbstract=null), Reference(id=1327013342104892088, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Faraj M, Schulz C. Buffered streaming graph partitioning[J]. ACM Journal of Experimental Algorithmics, 2022, 27(1): 1−26, articleTitle=null, refAbstract=null), Reference(id=1327013342163612345, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Tsourakakis C, Gkantsidis C, Radunovic B, et al. FENNEL: Streaming graph partitioning for massive scale graphs [C]// Proc of the 7th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2014: 333−342, articleTitle=null, refAbstract=null), Reference(id=1327013342226526906, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Prabhakaran V, Wu Ming, Weng Xuetian, et al. Managing large graphs on multi-cores with graph awareness [C]// Proc of the 2012 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2012: 41−52, articleTitle=null, refAbstract=null), Reference(id=1327013342314607291, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Awadelkarim A, Ugander J. Prioritized restreaming algorithms for balanced graph partitioning [C]// Proc of the 26th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2020: 1877−1887, articleTitle=null, refAbstract=null), Reference(id=1327013342381716157, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Patwary M, Garg S, Kang B. Window-based streaming graph partitioning algorithm [C/OL]// Proc of the 2019 Australasian Computer Science Week Multiconference. New York: ACM, 2019[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_M7eaf008a16906a5f79aM765510178163167&pageSize=25&index=1&searchId=16b73b1aa0124198b09f65fff2d40076&resultsCount=2&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick, articleTitle=null, refAbstract=null), Reference(id=1327013342444630718, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Faraj M, Schulz C. Buffered streaming graph partitioning[J]. ACM Journal of Experimental Algorithmics, 2022, 27(9): 1−26, articleTitle=null, refAbstract=null), Reference(id=1327013342507545279, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Hu Kekun, Zeng Guosun, Jiang Huawen, et al. Partitioning big graph with respect to arbitrary proportions in a streaming manner[J]. Future Generation Computer Systems, 2018, 80(1): 1−11, articleTitle=null, refAbstract=null), Reference(id=1327013342595625664, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Sun Zhipeng, Zeng Guosun, Ding Chunling, et al. A streaming graph partitioning method to achieve high cohesion and equilibrium via multiplayer repeated game[J]. IEEE Transactions on Computational Social Systems, 2022, 11(1): 803−814, articleTitle=null, refAbstract=null), Reference(id=1327013342683706049, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Pacaci A, Özsu M. Experimental analysis of streaming algorithms for graph partitioning [C]// Proc of the 2019 Int Conf on Management of Data. New York: ACM, 2019: 1375−1392, articleTitle=null, refAbstract=null), Reference(id=1327013342742426306, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Abbas Z, Kalavri V, Carbone P, et al. Streaming graph partitioning: An experimental study[J]. Proceedings of the VLDB Endowment, 2018, 11(11): 1590−1603, articleTitle=null, refAbstract=null), Reference(id=1327013342796952259, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Gottesbüren L, Heuer T, Sanders P, et al. Deep multilevel graph partitioning [C]// Proc of the 2021 European Symp on Algorithms. Wadern, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_M6ed4f62317f8aacca4fM60ed1017816328&pageSize=25&index=3&searchId=34b88e32991449758b0b66925964e1eb&resultsCount=4&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick, articleTitle=null, refAbstract=null), Reference(id=1327013342864061124, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Akhremtsev Y, Sanders P, Schulz C. High-quality shared-memory graph partitioning[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(11): 2710−2722, articleTitle=null, refAbstract=null), Reference(id=1327013342918587077, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Meyerhenke H, Sanders P, Schulz C. Parallel graph partitioning for complex networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(9): 2625−2638, articleTitle=null, refAbstract=null), Reference(id=1327013342985695942, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Battaglino C, Pienta R, Vuduc R. GraSP: Distributed streaming graph partitioning [C]// Proc of the 2015 High Performance Graph Mining. Barcelona, Spain: Barcelona Supercomputing Center, 2015[2023-04-21]. https://xueshu.baidu.com/usercenter/paper/show?paperid=9bb30523f8b9a6aa66ddf40fa944ca00&site=xueshu_se, articleTitle=null, refAbstract=null), Reference(id=1327013343052804807, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Hanai M, Suzumura T, Tan Wenjun, et al. Distributed edge partitioning for trillion-edge graphs[J]. Proceedings of the VLDB Endowment, 2019, 12(13): 2379−2392, articleTitle=null, refAbstract=null), Reference(id=1327013343124107976, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Mayer C, Mayer R, Tariq M, et al. Adwise: Adaptive window-based streaming edge partitioning for high-speed graph processing [C]// Proc of the 38th IEEE Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2018: 685−695, articleTitle=null, refAbstract=null), Reference(id=1327013343182828233, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Petroni F, Querzoni L, Daudjee K, et al. Hdrf: Stream-based partitioning for power-law graphs [C]// Proc of the 24th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2015: 243−252, articleTitle=null, refAbstract=null), Reference(id=1327013343283491530, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Sajjad H, Payberah A, Rahimian F, et al. Boosting vertex-cut partitioning for streaming graphs [C]// Proc of the 5th IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2016[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_4922c18f15887a4b174M79af10178163171&pageSize=25&index=1&searchId=9eb5c2ddc91c49e88880e18ea9b99248&resultsCount=1&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick, articleTitle=null, refAbstract=null), Reference(id=1327013343354794699, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Çatalyürek Ü, Devine K, Faraj M, et al. More recent advances in (hyper) graph partitioning[J]. ACM Computing Surveys, 2023, 55(12): 1−38, articleTitle=null, refAbstract=null), Reference(id=1327013343421903564, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Stanford University. SNAP dataset [DB/OL]. [2023-04-21]. http://snap.stanford.edu/data/index.html, articleTitle=null, refAbstract=null), Reference(id=1327013343493206733, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=Khorasani F, Gupta R, Bhuyan L. Scalable SIMD-efficient graph processing on GPUs [C]// Proc of the 24th Int Conf on Parallel Architecture and Compilation. Piscataway, NJ: IEEE, 2015: 39−50, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327013336006373985, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=1, ext=[AuthorCompanyExt(id=1327013336014762594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1327013336023151203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1清华大学计算机科学与技术系 北京 100084)]), AuthorCompany(id=1327013336111231588, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=2, ext=[AuthorCompanyExt(id=1327013336140591717, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336111231588, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2China Electronics Standardization Institute, Beijing 100007), AuthorCompanyExt(id=1327013336153174630, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336111231588, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国电子技术标准化研究院 北京 100007)]), AuthorCompany(id=1327013336232866407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=3, ext=[AuthorCompanyExt(id=1327013336249643624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3IEIT SYSTEMS Co., Ltd., Jinan 250101), AuthorCompanyExt(id=1327013336266420841, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3浪潮电子信息产业股份有限公司 济南 250101)])], figs=[ArticleFig(id=1327013338699117198, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 1, caption=Cold start problem of graph partitioning, figureFileSmall=YfFWgP7GYtEM/hEYcuALxg==, figureFileBig=o+FBfbfu+1cLxxenduq4rg==, tableContent=null), ArticleFig(id=1327013338875277967, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图1, caption=图划分冷启动问题, figureFileSmall=YfFWgP7GYtEM/hEYcuALxg==, figureFileBig=o+FBfbfu+1cLxxenduq4rg==, tableContent=null), ArticleFig(id=1327013339173073552, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 2, caption=Algorithm flow of distributed buffered streaming graph partitioning, figureFileSmall=Hv3ft6Bah+o79Xj3Eip9cA==, figureFileBig=XQVxFjzbnA+sJPw8tIT4pw==, tableContent=null), ArticleFig(id=1327013339244376721, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图2, caption=带缓冲区的分布式流式图划分算法流程, figureFileSmall=Hv3ft6Bah+o79Xj3Eip9cA==, figureFileBig=XQVxFjzbnA+sJPw8tIT4pw==, tableContent=null), ArticleFig(id=1327013339311485586, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 3, caption=Partition equalization comparison of different partitioning algorithms, figureFileSmall=9pAjXbVqbiUHMqkcZlsotw==, figureFileBig=n0zgVA7GQFcbuJagnkLzcg==, tableContent=null), ArticleFig(id=1327013339378594451, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图3, caption=不同划分算法划分均衡性对比, figureFileSmall=9pAjXbVqbiUHMqkcZlsotw==, figureFileBig=n0zgVA7GQFcbuJagnkLzcg==, tableContent=null), ArticleFig(id=1327013339445703316, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 4, caption=Partitioning cut edge ratio comparison of different partitioning algorithms, figureFileSmall=hx4UcVsn7Wy/YRsYLVqZhA==, figureFileBig=Zs2dLeeINw2CuIbTmpoTZA==, tableContent=null), ArticleFig(id=1327013339517006485, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图4, caption=不同划分算法划分割边比对比, figureFileSmall=hx4UcVsn7Wy/YRsYLVqZhA==, figureFileBig=Zs2dLeeINw2CuIbTmpoTZA==, tableContent=null), ArticleFig(id=1327013339600892566, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 5, caption=Total time comparison for partitioning of different partitioning algorithms, figureFileSmall=PoKhKKBitfhL1hhYk28giw==, figureFileBig=RTAKvcO/kJifmAxxpw3nMQ==, tableContent=null), ArticleFig(id=1327013339668001431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图5, caption=不同划分算法划分总时间对比, figureFileSmall=PoKhKKBitfhL1hhYk28giw==, figureFileBig=RTAKvcO/kJifmAxxpw3nMQ==, tableContent=null), ArticleFig(id=1327013339735110296, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 6, caption=Efficiency comparison of different partitioning algorithms, figureFileSmall=xsqqYPoFI6N6X4MamWIOgQ==, figureFileBig=0e3DYjYPZpibaaERRCbFtQ==, tableContent=null), ArticleFig(id=1327013339810607769, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图6, caption=不同划分算法效率对比, figureFileSmall=xsqqYPoFI6N6X4MamWIOgQ==, figureFileBig=0e3DYjYPZpibaaERRCbFtQ==, tableContent=null), ArticleFig(id=1327013339873522330, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Figure 7, caption=Proportion of data loading time in total partitioning time of different partitioning algorithms, figureFileSmall=Wtx1ZW47TUEA7AujFhd2xQ==, figureFileBig=KD2M7ev0RJnXHfNCFTqRKw==, tableContent=null), ArticleFig(id=1327013339944825499, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=图7, caption=不同划分算法的数据加载时间占总划分总时间比例, figureFileSmall=Wtx1ZW47TUEA7AujFhd2xQ==, figureFileBig=KD2M7ev0RJnXHfNCFTqRKw==, tableContent=null), ArticleFig(id=1327013340016128668, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 1, caption=Symble and Meaning, figureFileSmall=null, figureFileBig=null, tableContent=
符号含义
$ G $,$ {G_i} $,$ G_i^\tau $图、子图、时刻$ \tau $的子图
$ V $和$ E $顶点集和边集
$ v $和$ e $某个顶点和某条边
$ N\left( v \right) $顶点$ v $的邻居集
$ {\pi _k} $和$ \pi _k^\tau $$ k $路划分和时刻$ \tau $的$ k $路划分
$ E\left( {{G_i},{G_j}} \right) $割边集
$ {m_i} $和$ {b_i} $计算节点及其缓冲区
), ArticleFig(id=1327013340087431837, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表1, caption=

符号及含义

, figureFileSmall=null, figureFileBig=null, tableContent=
符号含义
$ G $,$ {G_i} $,$ G_i^\tau $图、子图、时刻$ \tau $的子图
$ V $和$ E $顶点集和边集
$ v $和$ e $某个顶点和某条边
$ N\left( v \right) $顶点$ v $的邻居集
$ {\pi _k} $和$ \pi _k^\tau $$ k $路划分和时刻$ \tau $的$ k $路划分
$ E\left( {{G_i},{G_j}} \right) $割边集
$ {m_i} $和$ {b_i} $计算节点及其缓冲区
), ArticleFig(id=1327013340167123614, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 2, caption=Information of Real-World Big Graph, figureFileSmall=null, figureFileBig=null, tableContent=
数据集顶点数边数顶点平均度数数据集类型
wiki-Talk2 394 3855 021 4104.2维基百科网络
LiveJournal4 847 57168 993 77328.5社交网络
Friendster65 608 3661 806 067 13555.1社交网络
), ArticleFig(id=1327013340230038175, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表2, caption=

真实大图信息

, figureFileSmall=null, figureFileBig=null, tableContent=
数据集顶点数边数顶点平均度数数据集类型
wiki-Talk2 394 3855 021 4104.2维基百科网络
LiveJournal4 847 57168 993 77328.5社交网络
Friendster65 608 3661 806 067 13555.1社交网络
), ArticleFig(id=1327013340305535648, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 3, caption=Information of Composite Big Graph, figureFileSmall=null, figureFileBig=null, tableContent=
尺度参数顶点数边数顶点平均度数
2667×1061.07×10932
27134×1062.14×10932
28268×1064.29×10932
29537×1068.58×10932
301 070×10617.1×10932
), ArticleFig(id=1327013340376838817, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表3, caption=

合成大图信息

, figureFileSmall=null, figureFileBig=null, tableContent=
尺度参数顶点数边数顶点平均度数
2667×1061.07×10932
27134×1062.14×10932
28268×1064.29×10932
29537×1068.58×10932
301 070×10617.1×10932
), ArticleFig(id=1327013340439753378, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 4, caption=Partition Quality Comparison of Different Partitioning Algorithms, figureFileSmall=null, figureFileBig=null, tableContent=
数据集KaMinParHeiStreamGraSPBH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $
注:KaMinPar和HeiStream均取非均衡因子$ \gamma = 0.03 $.
wiki-Talk1.0300.2931.0300.5614.9860.3972.2930.3432.3200.3322.2470.1932.3420.187
LiveJournal1.0300.0881.0300.2514.5340.2032.3530.1872.3530.1542.3980.0112.3690.009
Friendster1.0300.2561.0300.3174.4890.2512.3360.2322.3310.2172.3470.1822.3810.177
RMAT-261.0300.7881.0300.6104.4120.5511.9230.4501.9190.4231.9300.3521.9190.347
RMAT-271.0300.7891.0300.5964.2840.4941.8900.4401.8830.4121.8980.3611.8760.332
RMAT-281.0300.7871.0300.5864.1580.4761.7690.4171.7630.4031.7700.3441.7690.318
RMAT-291.0300.7891.0300.5744.0070.4211.7450.4221.7420.4091.7420.3521.7270.342
RMAT-301.0300.7901.0300.5693.9130.4961.7060.4111.7010.3971.7090.3411.7150.336
), ArticleFig(id=1327013340519445155, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表4, caption=

不同划分算法的划分质量对比

, figureFileSmall=null, figureFileBig=null, tableContent=
数据集KaMinParHeiStreamGraSPBH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $$ \rho $$ \lambda $
注:KaMinPar和HeiStream均取非均衡因子$ \gamma = 0.03 $.
wiki-Talk1.0300.2931.0300.5614.9860.3972.2930.3432.3200.3322.2470.1932.3420.187
LiveJournal1.0300.0881.0300.2514.5340.2032.3530.1872.3530.1542.3980.0112.3690.009
Friendster1.0300.2561.0300.3174.4890.2512.3360.2322.3310.2172.3470.1822.3810.177
RMAT-261.0300.7881.0300.6104.4120.5511.9230.4501.9190.4231.9300.3521.9190.347
RMAT-271.0300.7891.0300.5964.2840.4941.8900.4401.8830.4121.8980.3611.8760.332
RMAT-281.0300.7871.0300.5864.1580.4761.7690.4171.7630.4031.7700.3441.7690.318
RMAT-291.0300.7891.0300.5744.0070.4211.7450.4221.7420.4091.7420.3521.7270.342
RMAT-301.0300.7901.0300.5693.9130.4961.7060.4111.7010.3971.7090.3411.7150.336
), ArticleFig(id=1327013340586554020, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 5, caption=Partition Performance of Different Partitioning Algorithms, figureFileSmall=null, figureFileBig=null, tableContent=
$ k $KaMinParHeiStreamGraSPBH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $
150.43119.17519.94117.62121.10423.05423.453
258.1560.33821.9750.93410.5250.66311.4200.64112.7370.64413.7760.66913.6580.669
466.6880.16725.4180.2506.8840.6697.9740.6587.7410.6538.5970.6818.3860.681
865.7030.0908.9810.1155.5100.3696.2230.3625.9580.3526.5690.3626.4600.362
1655.2260.0478.8720.0574.4030.2095.1960.2025.5180.2045.7320.2115.3560.211
3250.8260.0289.7350.0293.7790.1064.5710.1054.5710.1034.9680.1044.8550.104
6480.9960.01217.8130.0146.0510.0417.1520.0397.0660.0397.3530.0427.1590.042
128253.410.001310.580.005281.080.005283.050.005288.040.005289.230.005291.110.005
), ArticleFig(id=1327013340670440101, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表5, caption=

不同划分算法划分性能对比

, figureFileSmall=null, figureFileBig=null, tableContent=
$ k $KaMinParHeiStreamGraSPBH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $$ \tau $$ \varepsilon $
150.43119.17519.94117.62121.10423.05423.453
258.1560.33821.9750.93410.5250.66311.4200.64112.7370.64413.7760.66913.6580.669
466.6880.16725.4180.2506.8840.6697.9740.6587.7410.6538.5970.6818.3860.681
865.7030.0908.9810.1155.5100.3696.2230.3625.9580.3526.5690.3626.4600.362
1655.2260.0478.8720.0574.4030.2095.1960.2025.5180.2045.7320.2115.3560.211
3250.8260.0289.7350.0293.7790.1064.5710.1054.5710.1034.9680.1044.8550.104
6480.9960.01217.8130.0146.0510.0417.1520.0397.0660.0397.3530.0427.1590.042
128253.410.001310.580.005281.080.005283.050.005288.040.005289.230.005291.110.005
), ArticleFig(id=1327013340762714790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 6, caption=Proportion of Data Loading Time in Total Partitioning Time of Different Partitioning Algorithms, figureFileSmall=null, figureFileBig=null, tableContent=
$ k $HeiStreamGraSPBH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $
16.8330.3563.9210.1963.4650.1964.1710.1974.8310.2094.6280.219
27.5170.3422.0840.1982.2330.1952.5060.1962.7530.1992.6640.209
47.6710.3011.3650.1981.5570.1951.5080.1941.7080.1981.6650.215
82.6680.2971.0740.1941.2270.1971.1840.1981.2840.1951.2770.214
162.6180.2950.8700.1971.0250.1971.0410.1881.1750.2041.0460.189
322.6400.2710.7530.1990.9100.1990.9100.1990.9960.2000.9570.209
645.2320.2931.1880.1961.4010.1951.4010.1981.4510.1971.4230.201
1287.9720.02556.1060.19957.2520.20258.3790.20259.1130.20459.0050.204
), ArticleFig(id=1327013340842406567, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表6, caption=

不同划分算法的数据加载时间占总划分总时间比例

, figureFileSmall=null, figureFileBig=null, tableContent=
$ k $HeiStreamGraSPBH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $$ {\tau _{\rm ld}} $$ {{{\tau _{\rm ld}}} \mathord{\left/ {\vphantom {{{\tau _{\rm ld}}} \tau }} \right. } \tau } $
16.8330.3563.9210.1963.4650.1964.1710.1974.8310.2094.6280.219
27.5170.3422.0840.1982.2330.1952.5060.1962.7530.1992.6640.209
47.6710.3011.3650.1981.5570.1951.5080.1941.7080.1981.6650.215
82.6680.2971.0740.1941.2270.1971.1840.1981.2840.1951.2770.214
162.6180.2950.8700.1971.0250.1971.0410.1881.1750.2041.0460.189
322.6400.2710.7530.1990.9100.1990.9100.1990.9960.2000.9570.209
645.2320.2931.1880.1961.4010.1951.4010.1981.4510.1971.4230.201
1287.9720.02556.1060.19957.2520.20258.3790.20259.1130.20459.0050.204
), ArticleFig(id=1327013340917904040, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 7, caption=Impact of Different Buffer Zone Sizes on Partitioning Quality and Performance, figureFileSmall=null, figureFileBig=null, tableContent=
$ \omega $BH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ \rho $$ \lambda $$ \tau $$ \rho $$ \lambda $$ \tau $$ \rho $$ \lambda $$ \tau $$ \rho $$ \lambda $$ \tau $
1282.3690.1823.0392.3750.1512.8182.4210.0102.9012.3580.0092.896
2562.3470.1872.9742.3530.1562.8102.3980.0112.8912.3470.0092.845
5122.3470.1872.8132.3470.1572.7962.3920.0112.8442.3360.0102.841
10242.3470.1872.7932.3520.1542.7922.3980.0112.8052.3700.0092.802
20482.3470.1872.8402.3470.1572.7802.3870.0122.8032.3360.0112.798
), ArticleFig(id=1327013341001790121, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表7, caption=

不同缓冲区大小对划分质量和性能的影响

, figureFileSmall=null, figureFileBig=null, tableContent=
$ \omega $BH(本文)BB(本文)BWM(本文)Hybrid(本文)
$ \rho $$ \lambda $$ \tau $$ \rho $$ \lambda $$ \tau $$ \rho $$ \lambda $$ \tau $$ \rho $$ \lambda $$ \tau $
1282.3690.1823.0392.3750.1512.8182.4210.0102.9012.3580.0092.896
2562.3470.1872.9742.3530.1562.8102.3980.0112.8912.3470.0092.845
5122.3470.1872.8132.3470.1572.7962.3920.0112.8442.3360.0102.841
10242.3470.1872.7932.3520.1542.7922.3980.0112.8052.3700.0092.802
20482.3470.1872.8402.3470.1572.7802.3870.0122.8032.3360.0112.798
), ArticleFig(id=1327013341085676202, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=EN, label=Table 8, caption=Advantages, Disadvantages and Application Scenarios of Different Heuristics, figureFileSmall=null, figureFileBig=null, tableContent=
特性BH(本文)BB(本文)BWM(本文)Hybrid(本文)
优点简单高效划分均衡性好划分模块度高、均衡性好拓扑结构感知、划分割边比低、均衡性好
缺点划分割边比高划分割边比高计算复杂计算复杂
适用场景实时性要求高、负载均衡敏感、
通信开销不敏感的图计算场景
实时性要求高、负载均衡敏感、
通信开销不敏感的图计算场景
实时性要求低、负载均衡和
通信开销敏感的图计算场景
实时性要求低、负载均衡和
通信开销敏感的图计算场景
), ArticleFig(id=1327013341165367979, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, language=CN, label=表8, caption=

不同启发式规则的优缺点以及适用场景

, figureFileSmall=null, figureFileBig=null, tableContent=
特性BH(本文)BB(本文)BWM(本文)Hybrid(本文)
优点简单高效划分均衡性好划分模块度高、均衡性好拓扑结构感知、划分割边比低、均衡性好
缺点划分割边比高划分割边比高计算复杂计算复杂
适用场景实时性要求高、负载均衡敏感、
通信开销不敏感的图计算场景
实时性要求高、负载均衡敏感、
通信开销不敏感的图计算场景
实时性要求低、负载均衡和
通信开销敏感的图计算场景
实时性要求低、负载均衡和
通信开销敏感的图计算场景
)], 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.202330386, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330386, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202330386, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202330386, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1751299200000, fullTextJson=null, articleText=null, reference=null)
收藏切换
一种带缓冲区的分布式流式图划分算法
史惠康 1 , 王泽胜 2 , 胡克坤 3 , 董刚 3 , 赵有健 1, *
计算机研究与发展 | 高性能计算 2025,62(7): 1805-1815
收起
收藏切换
计算机研究与发展 |高性能计算 2025 , 62 (7) : 1805 -1815
一种带缓冲区的分布式流式图划分算法
全屏
[Author(id=1327013336346112619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=shk@pku.org.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327013336463553133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336346112619, language=EN, stringName=Huikang Shi, firstName=Huikang, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084, bio={"content":"

born in 1975. PhD. His main research interest includes electronic and information

"}, bioImg=null, bioContent=

born in 1975. PhD. His main research interest includes electronic and information

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013336530661998, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336346112619, 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清华大学计算机科学与技术系 北京 100084, bio={"img":"4tVEfVspwTRRYbFHfjcrdg==","content":"

1975年生. 博士. 主要研究方向为电子与信息

"}, bioImg=4tVEfVspwTRRYbFHfjcrdg==, bioContent=

1975年生. 博士. 主要研究方向为电子与信息

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336006373985, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=1, ext=[AuthorCompanyExt(id=1327013336014762594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1327013336023151203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1清华大学计算机科学与技术系 北京 100084)])]), Author(id=1327013336698434160, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=1327013336773931634, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336698434160, language=EN, stringName=Zesheng Wang, firstName=Zesheng, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2China Electronics Standardization Institute, Beijing 100007, bio={"content":"

born in 1987. PhD, senior engineer. His main research interests include cloud computing, and information technology service

"}, bioImg=null, bioContent=

born in 1987. PhD, senior engineer. His main research interests include cloud computing, and information technology service

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013336874594931, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336698434160, language=CN, stringName=王泽胜, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2中国电子技术标准化研究院 北京 100007, bio={"img":"i//5m1ZBfvNqBlIC1e8riA==","content":"

1987年生. 博士,高级工程师. 主要研究方向为云计算、信息技术服务

"}, bioImg=i//5m1ZBfvNqBlIC1e8riA==, bioContent=

1987年生. 博士,高级工程师. 主要研究方向为云计算、信息技术服务

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336111231588, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=2, ext=[AuthorCompanyExt(id=1327013336140591717, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336111231588, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2China Electronics Standardization Institute, Beijing 100007), AuthorCompanyExt(id=1327013336153174630, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336111231588, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2中国电子技术标准化研究院 北京 100007)])]), Author(id=1327013336945898101, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, orderNo=2, 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=1327013337025589879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336945898101, language=EN, stringName=Kekun Hu, firstName=Kekun, middleName=null, lastName=Hu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3IEIT SYSTEMS Co., Ltd., Jinan 250101, bio={"content":"

born in 1987. PhD, senior engineer. Member of CCF. His main research interests include graph processing and graph deep learning

"}, bioImg=null, bioContent=

born in 1987. PhD, senior engineer. Member of CCF. His main research interests include graph processing and graph deep learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013337147224696, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013336945898101, language=CN, stringName=胡克坤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3浪潮电子信息产业股份有限公司 济南 250101, bio={"img":"tlPRuliuf1qCF0Q5Z4QXig==","content":"

1987年生. 博士,高级工程师. CCF会员. 主要研究方向为图计算、图深度学习

"}, bioImg=tlPRuliuf1qCF0Q5Z4QXig==, bioContent=

1987年生. 博士,高级工程师. CCF会员. 主要研究方向为图计算、图深度学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336232866407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=3, ext=[AuthorCompanyExt(id=1327013336249643624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3IEIT SYSTEMS Co., Ltd., Jinan 250101), AuthorCompanyExt(id=1327013336266420841, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3浪潮电子信息产业股份有限公司 济南 250101)])]), Author(id=1327013337226916474, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, 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=1327013337327579772, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337226916474, language=EN, stringName=Gang Dong, firstName=Gang, middleName=null, lastName=Dong, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3IEIT SYSTEMS Co., Ltd., Jinan 250101, bio={"content":"

born in 1979. PhD, senior engineer. Member of CCF. His main research interests includes FPGA design, architecture and applications

"}, bioImg=null, bioContent=

born in 1979. PhD, senior engineer. Member of CCF. His main research interests includes FPGA design, architecture and applications

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013337398882941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337226916474, language=CN, stringName=董刚, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=3, address=3浪潮电子信息产业股份有限公司 济南 250101, bio={"img":"JbPtjMW4hPxLJ7N6seUrXw==","content":"

1979年生. 博士,高级工程师. CCF会员. 主要研究方向为FPGA芯片架构设计及其应用

"}, bioImg=JbPtjMW4hPxLJ7N6seUrXw==, bioContent=

1979年生. 博士,高级工程师. CCF会员. 主要研究方向为FPGA芯片架构设计及其应用

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336232866407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=3, ext=[AuthorCompanyExt(id=1327013336249643624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3IEIT SYSTEMS Co., Ltd., Jinan 250101), AuthorCompanyExt(id=1327013336266420841, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336232866407, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3浪潮电子信息产业股份有限公司 济南 250101)])]), Author(id=1327013337470186111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zhaoyoujian@tsinghua.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327013337545683585, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337470186111, language=EN, stringName=Youjian Zhao, firstName=Youjian, middleName=null, lastName=Zhao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084, bio={"content":"

born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

"}, bioImg=null, bioContent=

born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327013337616986754, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, authorId=1327013337470186111, 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清华大学计算机科学与技术系 北京 100084, bio={"img":"scJ7dbmy7vjGqggAjH0hdA==","content":"

1969年生. 博士,教授,博士生导师. 主要研究方向为高速互联网体系结构、交换与路由、高速网络设备

"}, bioImg=scJ7dbmy7vjGqggAjH0hdA==, bioContent=

1969年生. 博士,教授,博士生导师. 主要研究方向为高速互联网体系结构、交换与路由、高速网络设备

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327013336006373985, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, xref=1, ext=[AuthorCompanyExt(id=1327013336014762594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1327013336023151203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327013332390883909, companyId=1327013336006373985, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1清华大学计算机科学与技术系 北京 100084)])])]
史惠康1 , 王泽胜2, 胡克坤3, 董刚3, 赵有健1, *
作者信息
  • 1清华大学计算机科学与技术系 北京 100084
  • 2中国电子技术标准化研究院 北京 100007
  • 3浪潮电子信息产业股份有限公司 济南 250101
通讯作者:
作者简介:

1975年生. 博士. 主要研究方向为电子与信息

1987年生. 博士,高级工程师. 主要研究方向为云计算、信息技术服务

1987年生. 博士,高级工程师. CCF会员. 主要研究方向为图计算、图深度学习

1979年生. 博士,高级工程师. CCF会员. 主要研究方向为FPGA芯片架构设计及其应用

1969年生. 博士,教授,博士生导师. 主要研究方向为高速互联网体系结构、交换与路由、高速网络设备

A Distributed Buffered Streaming Graph Partitioning Algorithm
Huikang Shi1 , Zesheng Wang2, Kekun Hu3, Gang Dong3, Youjian Zhao1, *
Affiliations
  • 1Department of Computer Science and Technology, Tsinghua University, Beijing 100084
  • 2China Electronics Standardization Institute, Beijing 100007
  • 3IEIT SYSTEMS Co., Ltd., Jinan 250101
  • born in 1975. PhD. His main research interest includes electronic and information

    born in 1987. PhD, senior engineer. His main research interests include cloud computing, and information technology service

    born in 1987. PhD, senior engineer. Member of CCF. His main research interests include graph processing and graph deep learning

    born in 1979. PhD, senior engineer. Member of CCF. His main research interests includes FPGA design, architecture and applications

    born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

出版时间: 2025-07-01 doi: 10.7544/issn1000-1239.202330386
文章导航
收藏切换

图划分是大图并行处理关键技术之一. 现有图划分算法存在划分质量和效率难以平衡的问题,主要体现在离线划分算法划分质量高但耗时长;在线(也称流式)划分算法相对高效但划分质量不理想. 为此,提出一种带缓冲区的分布式流式划分算法. 该算法采用多加载器-多划分器架构,多个加载器并行读取图数据,提高图数据加载效率;每个划分器维护一个缓冲区,缓存相应加载器发来的图顶点,并按顶点度数高低排序,为划分器提供更多决策依据. 划分器预置有4条流式启发式规则,围绕不同目标,对缓冲区中的顶点实施并行划分,并借助重流机制微调划分结果,改进划分质量. 分布式系统环境下的划分质量与性能实验表明:提出算法的划分质量(割边比)比当前最好的在线划分算法改善超过18.8个百分点,并将图数据加载时间在划分总时间的占比,从单划分器-单加载器架构流式划分算法的平均30.8%缩减至平均20.1%.

大图  /  流式划分  /  分布式  /  缓冲  /  重流

Graph partitioning is a key technique for parallel processing of big graphs. Existing graph partitioning algorithms struggle to balance partition quality and efficiency. Offline partitioning algorithms tend to achieve high partition quality but are time-consuming, while online (or streaming) partitioning algorithms are relatively efficient but suffer from suboptimal partition quality. To address the above problem, we propose a distributed streaming partitioning algorithm with a buffering mechanism in this paper. The algorithm utilizes a multi-loader and multi-partitioner architecture, where multiple loaders read graph data in parallel to improve loading efficiency. Each partitioner maintains a buffer to store graph vertices received from the corresponding loader and sorts them in descending order based on vertex degree, providing better decision-making data for partitioning. Four streaming heuristic rules are pre-configured in the partitioners, which perform parallel partitioning on vertices in the buffer with different goals in mind. A reflow mechanism is employed to fine-tune the partitioning results and improve quality. Experimental results in a distributed system environment show that the proposed algorithm improves partition quality (edge-cut ratio) by more than 18.8% compared with the best existing online partitioning algorithm. Additionally, it reduces the proportion of graph data loading time in the total partitioning time from an average of 30.8% in a single-loader single-partitioner architecture to an average of 20.1%.

big graph  /  streaming partitioning  /  distributed  /  buffering  /  restreaming
史惠康, 王泽胜, 胡克坤, 董刚, 赵有健. 一种带缓冲区的分布式流式图划分算法. 计算机研究与发展, 2025 , 62 (7) : 1805 -1815 . DOI: 10.7544/issn1000-1239.202330386
Huikang Shi, Zesheng Wang, Kekun Hu, Gang Dong, Youjian Zhao. A Distributed Buffered Streaming Graph Partitioning Algorithm[J]. Journal of Computer Research and Development, 2025 , 62 (7) : 1805 -1815 . DOI: 10.7544/issn1000-1239.202330386
伴随着数字经济的蓬勃发展,移动互联网、智能终端越发普及,社交网络、智慧交通和生命科学等领域涌现出海量数据[1]. 这些数据规模大,数据元素间关联关系复杂,业界称为图大数据,简称大图. 以全球最大的社交平台Facebook为例,其社交网络拥有超过20亿用户和上千亿条好友关系. 传统的单机由于性能有限,难以从大图中快速挖掘蕴藏的价值,需要拥有强大计算与存储能力的并行计算系统作为支撑. 为充分利用并行计算系统开展大图并行处理,首先要对大图实施划分.
图划分,是指按照某种策略将大图划分为若干个满足一定约束条件的子图. 子图规模均衡性和子图割边数量,是影响大图分布式并行处理性能和效率的重要因素[2],主要体现在:规模越均衡、割边数越少,映射到各计算节点的负载越均衡、节点间通信代价越低、处理效率越高. 如何获取均衡性好、割边数少的图划分结果,已成为业界关注的重点[3-4]. 国内外学者提出许多图划分算法,主要有离线划分、分布式划分和流式划分. 离线划分算法在实施划分前,将大图全部加载到内存,典型代表有谱划分算法[5]和Metis划分算法[6]. 这类图划分算法依据图全局信息实现高质量划分,但时间复杂度高且受内存大小限制,常用于划分小规模图数据. 伴随着图数据规模的持续增大,分布式划分和流式划分逐渐成为研究热点[7-8]. 其中,分布式划分算法充分利用并行计算系统中多个处理节点的算力和存储资源,依据图全局信息实施划分,如ParMetis划分算法[9]. 流式划分算法采用边加载边划分的策略,不依赖图全局信息,具有时间复杂度低的特点,典型代表有LDG[10],FENNEL[11],HeiStream[12]. 该类图划分算法通常采用单加载器-单划分器结构,存在性能瓶颈,且由于缺乏图全局信息,存在冷启动问题,即在划分初始阶段,划分器的部分顶点因缺乏划分决策信息,难以获取最优子图位置编号,导致划分质量不理想. 如图1所示,采用LDG启发式规则将大图划分为2个子图,假设按照顺序加载,且每个子图中最大顶点数为4,将得到划分结果1(有4条割边),但实际最优结果应为划分结果2(有2条割边). 之所以出现偏差,主要因为该启发式规则并未充分利用高度数顶点等图数据流中的有价值信息.
针对上述问题,本文提出一种带缓冲区的分布式流式划分算法. 该算法采用多加载器-多划分器架构,各加载器以顶点为单位,按照特定顺序并行加载图数据;各划分器维护一个缓存,对相应加载器输出的图顶点流数据先缓存,然后按顶点度数重新排序,并依据不同划分目标实施划分. 在充分利用缓冲区辅助信息提高划分质量的同时,借助分布式流式机制提高划分算法性能. 为进一步提高划分质量,我们借助重流机制对划分结果进行微调优化. 本文的创新点及贡献有4个方面:
1)设计一种多加载器-多划分器的分布式图划分架构. 通过多个加载器和多个划分器分别并行读取和划分图数据,提高图数据的加载效率和划分效率,缓解传统流式划分算法存在的性能瓶颈.
2)提出一种分布式图数据缓冲机制. 每个划分器维护一个缓冲区,采用快速排序算法对缓冲区内图数据按照顶点度数由高到低排序,优先将高度数顶点作为“种子”实施划分,有效缓解冷启动问题.
3)设计4条流式启发式规则. 分别以最优均衡性、简单高效原则、最大化模块度兼顾均衡性、最小化割边比兼顾均衡性为目标,将大图划分为一系列小规模子图,可以满足不同应用场景下的划分需求.
4)在真实的分布式系统中开展一系列实验,全面检验所提算法划分真实大图与合成大图的划分质量和划分性能.
图划分算法主要包括3类:离线划分、流式划分和分布式划分. 谱划分[5]是典型的离线划分算法,它首先计算相似矩阵的拉普拉斯矩阵,然后求出其第2大特征值及其对应的特征向量,对图进行递归二分. 该算法对很多类型的图数据都能生成高质量划分结果. Metis[6]采用多级$ k $路划分策略,将图划分为3个阶段:1)第1阶段通常借助收缩匹配或聚簇等策略来构建输入图的连续粗略近似,组成层次化结构;2)一旦图只剩下少数几个顶点,第2阶段借助常用的离线图划分算法直接将其划分为$ k $个子图;3)第3阶段将该划分结果连续投影到层次结构中的更精细级别,并使用局部搜索算法对划分结果进行细化. 与谱划分类似,Metis[6]计算开销较大,不便用来划分大规模图数据. 例如,Tsourakakis等人[13]采用Metis对拥有超过14亿条边的Twitter图进行划分,其划分总时长超过8.5 h.
在流式划分方面,Stanton等人[10]将流模型引入到图划分,并提出包含LDG在内的10条流式启发式规则,在数据由磁盘加载到内存的一次性过程中,仅利用图局部信息即可实施划分. Tsourakakis等人[13]在文献[10]的基础上,定义一个融合LDG和Folklore[14]两种启发式规则的流式划分框架FENNEL,将顶点分配到具有更多邻居的子图. Nishimura等人[11]提出重流思想,并设计了LDG和FENNEL的重流版本,它们保持图划分目标函数不变,并以上一轮流式划分的结果作为本轮的初始划分,对划分结果不断微调优化,主要适用于相同或相近的大图持续出现的场景. Awadelkarim等人[15]研究顶点顺序对流式划分质量的影响,根据特定优先级对流式加载的顶点进行静态或动态排序,并提出LDG的优先级版本reLDG. Patwary等人[16]提出基于贪心策略的流式划分算法,设计含有数百个顶点的滑动窗口,为候选顶点提供更多辅助信息. 类似地,Faraj等人[17]提出带缓冲区的流式划分算法,首先构建代表批处理顶点和已划分顶点的结构模型图,再利用传统多级图划分算法完成划分. Zeng等人[18]提出非均衡流式划分算法,可按照任意比例关系流式地将大图划分为一系列子图. Sun等人[19]将博弈理论与流式划分相结合,采用多人博弈纳什均衡,实现各个时间窗口内流数据的最优划分. 这些流式划分算法均采用单加载器-单划分器架构,容易出现性能瓶颈. 此外,Özsu等人[20]、Abbas等人[21]关注流式划分算法的性能评测问题.
在分布式划分方面,许多学者基于多级图划分范式设计了划分算法,如基于共享内存的KaMinPar[22],Mt-KaHIP[23]和基于分布式内存的ParMetis[9],ParHIP[24]等. 其中,KaMinPar[22]进一步将多级算法延伸到初始划分阶段,结合递归二分和直接$ k $路划分计算初始划分方案. Mt-KaHIP[23]将多级图划分算法与KaHIP图划分工具相结合,旨在提供适用于大规模图数据的高质量图划分解决方案. ParMetis[9]是Metis[6]的并行扩展版本,专门用于处理大规模图数据的划分和排序问题,旨在优化分布式内存体系结构上的性能. ParHIP[24]是一种用于超图划分的并行算法,同时支持共享内存和分布式内存计算环境. 总的来说,基于共享内存的分布式划分算法[22-23]可实现较高的划分质量和合理的可扩展性,但基于分布式内存的分布式划分算法[9]划分质量依然不高,且可扩展性低、难以保证划分均衡性. 此外,Battaglino等人[25]则积极尝试并行化流式划分算法,在FENNEL算法的基础上提出了分布式流式划分算法GraSP,这是当前性能最好的分布式划分算法.
上述划分算法[10,13,15-17,19,24-25]均属于割边划分,还有部分算法专注于割点划分[26-29],这类算法用连接边流替代顶点流作为输入,目标通常是最小化割点数. 尽管从应用角度来看,它们与本文研究工作密切相关,但该类问题并不是本文工作的重点. 更多有关图划分工作请参考文献[30].
图划分按照某种方式将大图$ G $切割成多个小的子图$ {G_i}\left( {i \in \left\{ {1,{\text{2}},…,k} \right\}} \right) $,即$ G = {G_1} \cup {G_2} \cup…\cup {G_k} $. 设大图$ G = \left( {V,E} \right) $, 其中$ V = \left\{ {{v_1},{v_2},…,{v_n}} \right\} $,$ E = \left\{ {{e_{ij}}|{v_i},{v_j} \in V} \right\} $分别代表其顶点集和连接边集,$ n $为顶点数. $ \forall {v_j} \in V $,将与其关联的连接边条数称为度数,记为$ deg\left( {{v_j}} \right) $;与$ {v_j} $有连接边相连的顶点集合称为邻居,记为$ N\left( {{v_j}} \right) = \left\{ {{v_k}|{v_k} \in V \wedge {e_{jk}} \in E} \right\} $,则有$ deg\left( {{v_j}} \right) = \left| N\left( {{v_j}} \right) = \big\{ {v_k} \in V \wedge {e_{jk}} \in E \big\} \right| $. $ \forall i \in \left\{ {1,{\text{2}},…,k} \right\} $,$ {G_i} = \left( {{V_i},{E_i}} \right) $是$ G $的一个子图,并满足$ {V_i} \subseteq V $和$ {E_i} \subseteq E $. 这些子图集合$ {\pi _k} = \{ {G_1},{G_2},…, {G_k} \} $为$ G $的一个$ k $路划分,当且仅当$ {\forall _{i,j}} \in \left\{ {1,2,…,k} \right\} $,$ i \ne j $,均有$ {V_i} \cap {V_j} = \varnothing $‌,$ V = \mathop \cup \limits_{i = 1}^k {V_i} $,$ E = \mathop \cup \limits_{i = 1}^k {E_i} $. 横跨2个子图$ {G_i} $和$ {G_j} $的连接边称为割边,上述2个子图的割边集记为$ E\left( {{G_i},{G_j}} \right) $.
图划分问题就是:给定大图$ G $,寻找它的一个$ k $路划分$ \pi _k^ * = \left\{ {G_1^ * ,G_2^ * ,…,G_k^ * } \right\} $,使得对于$ k $路划分空间$ \varOmega $中的任一划分$ {\pi _k} $,在保证各子图顶点数均衡的前提下,割边数最少. 该问题可形式化描述为式(1)和式(2).
$ f\left( {{\pi _k}} \right) = \arg \min \sum\limits_{{G_i},{G_j} \in {\pi _k}} {\;\;\left| {E\left( {{G_i},{G_j}} \right)} \right|} \text{,} $
$ \mathrm{s}.\mathrm{t}.\left|1-\frac{V_i}{V}\right|\leqslant\varepsilon\text{,}\forall i\in\left\{1,2,…,k\right\}. $
本文用到的主要符号及其含义如表1所示.
不同划分算法的划分质量参差不齐. 这里采用业界常用的划分质量评价指标来构建评价体系,主要包括:
1)均衡性$ \rho = \mathop {\max }\limits_{i \in \left\{ {1,2,…,k} \right\}} \left( |V_i|/(|V|\cdot k) \right) $,用来度量子图顶点数以及理想情况下每个子图应拥有的顶点数的偏离程度. 偏离理想值1.0越大,意味着并行处理阶段各节点间负载越不均衡,处理时间越长.
2)割边比$ \lambda = \dfrac{1}{{| E |}}{{\left| {\mathop \cup \limits_{i = 1,j = 1}^k E\left( {{G_i},{G_j}} \right)} \right|}} $,用来度量划分$ {\pi _k} $的割边数占总边数的比例,$ \lambda $值越大,并行处理阶段各处理节点间的通信开销越大,处理时间越长.
3)划分总时间$ \tau = \mathop {\max }\limits_{i \in \left\{ {1,2,…,k} \right\}} \left( {{\tau _{i,{\mathrm{ld}}}} + {\tau _{i,{\mathrm{part}}}}} \right) $. 其中,$ \tau_{i,\mathrm{ld}} $和$ \tau_{i,\mathrm{part}} $分别表示第$ i \in \left\{ {1,2,…,k}\right\} $个划分进程的数据加载时间和划分时间. 对于采用单加载器-单划分器的流式划分算法以及离线图划分算法而言,其划分总时间$ \tau = {\tau _{{\mathrm{ld}}}} + {\tau _{{\mathrm{part}}}} $,$ {\tau _{{\mathrm{ld}}}} $和$ {\tau _{{\mathrm{part}}}} $分别表示数据加载时间和划分时间.
4)效率$ \varepsilon=\dfrac{\tau_{\mathrm{seq}}}{proc\times\tau_{\mathrm{par}}} $. 其中,$ \tau\mathrm{_{seq}} $和$ \tau_{\mathrm{par}} $分别表示划分进程数$ proc = 1 $和$ proc \gt 1 $时的划分总时间.$ \varepsilon $用来表征图数据规模不变的情况下,划分总时间随划分进程数增加的变化情况. $ \varepsilon $值越接近于1.0,表示效率越高,即并行计算资源有效利用率越高.
流式划分算法中普遍存在冷启动问题. 为缓解该问题,本节提出带缓冲区的分布式流式划分算法. 具体工作流程如图2所示.
本文算法采用多加载器-多划分器架构,运行于分布式系统的不同处理节点上. 不妨设分布式系统由$ k $个同构计算节点组成,节点间通过高速通信链路连接,记所有节点集合为$ M = \left\{ {{m_1},{m_2},…,{m_k}} \right\} $. 其中,每个计算节点上运行1对加载器-划分器,加载器负责从分布式文件系统中读取大图$ G = \left( {V,E} \right) $,并传递给随后的划分器,因而共有$ k $对加载器-划分器. 每个划分器维护一个大小为$ w $的缓冲区,用以存放图数据流. 每个划分器都保存一份划分决策信息$ \pi _k^\tau $,即时刻$ \tau $大图$ G $的$ k $路划分.
$ k $个加载器按照随机原则,以顶点为单位从文件系统中成批并行读取$ w $个图顶点,并发送给相应划分器;划分器首先缓存收到的图数据流,待缓冲区满后,利用快速排序算法对缓冲区内的图顶点按照度数由高到底排序;随后根据所提4条启发式规则BH(buffered hashing),BB(buffered balance),BWM(buffered weighted modularity),Hybrid(3.2节中介绍)中的某一条,计算缓冲区内各个顶点应放置到右侧分布式系统的哪个处理节点上并实施放置;重复上述过程$ ceil\left( {{n \mathord{\left/ {\vphantom {n w}} \right. } w}} \right) $批次,直至数据加载完毕时,$ G $被划分为$ k $个子图. 其中,$ ceil\left( * \right) $表示向上取整函数,$ n $为$ G $的顶点数. 最后,将已有划分方案作为已知信息,采用重流方式,对划分方案微调以提高划分质量. 具体算法如算法1所示.
算法 1. 分布式流式图划分.
输入:$ G $,$ k $,$ {b_i} $,$ w $,num_streams;
输出:$ \pi _k^\tau $.
① num_batches←$ceil(n/w) $;
② $b_i $←$\varnothing $;
③ $\tau $←0;
④ initialize(num_streams);
⑤ initialize($\pi _k^\tau $, $\varnothing $);
⑥ for each s in {1, 2, …, num_streams}
⑦  for each batch l in {1, 2, …, num_batches}
⑧   for each partitioning process $p_i $ in {1, 2, …, k} do in parallel /*各划分器$p_i $并行执行*/
⑨     $b_i $←qucikSort_vertexDegree($b_i $);/*用快 排算法对缓冲区中的顶点按照度数 非递增排序*/
⑩    for each vertex v in buffer bi
⑪      j←streamingHeuristic(v, $\pi _k^\tau $);/*根据启 发式规则计算顶点应放置的子图 编号*/
⑫      $G_j^{\tau + 1} $←v;/*放入对应子图*/
⑬    end for
⑭   end for
⑮    $\pi _k^{\tau + w} $←MPI_partitionUpdate($\pi _k^\tau $);/*各划分 器同步各个子图的最新状态*/
⑯    $\tau $←$\tau + w $;
⑰  end for
⑱ end for
不妨设$ \pi _k^\tau = \left\{ {G_1^\tau ,G_2^\tau ,…,G_k^\tau } \right\} $为时刻$ \tau $大图$ G $的$ k $路划分. 其中$ G_i^\tau \left( {i \in \left\{ {1,2,…,k} \right\}} \right) $表示时刻$ \tau $子图$ {G_i} $的状态. 每个划分器$ {p_i}\left( {i \in \left\{ {1,2,…,k} \right\}} \right) $所维护的缓冲区$ {b_i}( i \in \left\{ {1,2,…,k} \right\} ) $中存放已按度数由高到低有序排列的顶点,记为$ \left\{ {v_{i1}^\tau ,v_{i2}^\tau ,…,v_{iw}^\tau } \right\} $. 时刻$ \tau + 1 $,划分器$ {p_i}( i \in \{ 1, 2,…, k \} ) $基于当前的划分决策信息$ \pi _k^\tau $,按照某种启发式规则,决定缓冲区$ {b_i} $中某个顶点$ v $应“流”向哪个子图. 待缓冲区内所有顶点分配完毕,各划分器同步更新$ \pi _k^\tau $. 若出现多个划分器同时更新某一子图$ G_k^\tau $的状态,则按照划分器编号由小到大的顺序按序更新. 重复上述过程直至所有顶点加载完毕,即可得到$ G $的$ k $路划分$ {\pi _k} $. 将$ {\pi _k} $作为已知信息,对图数据$ G = \left( {V,E} \right) $实施重流,利用支持重流的启发式规则进一步优化$ {\pi _k} $.
本节设计了4条分布式流式启发式规则,每个规则分别对应一个算法. 各个划分器并行执行,用以确定各自缓冲区中当前顶点$ v $应放置的子图编号$ ind $.
1)BH. 按照简单高效原则实施划分,尽可能提高划分效率. 设计哈希函数$ H:{B_i} \to \left\{ {1,{\text{2}},…,k} \right\} $,将缓冲区中最新的顶点$ {v_{\mathrm{g}}} $分配给子图,子图编号为$ ind $:
$ {{ind}} = H\left( {{v_{\mathrm{g}}}} \right) + 1 \text{,} $
本文取$ H\left( {{v_{\mathrm{g}}}} \right) = {v_{\mathrm{g}}}\text{mod} k $.
2)BB. 按照最优均衡性目标实施划分. 在时刻$ \tau $,将缓冲区中最新的顶点$ {v_{\mathrm{g}}} $“流”向当前已分配顶点数最少的子图$ G_i^\tau $. 若存在多个具有最少顶点数的子图,则随机指派$ {v_{\mathrm{g}}} $到其中任一子图,子图编号为:
$ ind = \mathop {\arg \min}\limits_{i \in \left\{ {1,2,…,k} \right\}} \left( {\left| {V_i^\tau } \right|} \right). $
BH和BB启发式规则不便利用上一次流式划分的结果来指导当前流中顶点的划分,因而重流效果不明显.
3)BWM. 在兼顾最优均衡性原则的同时,按照最大化子图模块度目标实施划分. 在时刻$ t $,将缓冲区中最新的顶点$ {v_{\mathrm{g}}} $“流”向某个子图,使得:①$ {v_{\mathrm{g}}} $的邻居顶点集与子图$ G_i^\tau $顶点集交集阶数最大;②添加惩罚函数项以惩罚顶点数多的子图,从而避免失衡. 若2个或多个子图的模块度相等,则随机指派$ {v_{\mathrm{g}}} $到其中任一子图:
$ ind = \mathop {\arg \max \left( {\left| {N\left( {{v_{\mathrm{g}}}} \right) \cap V_i^\tau } \right| \times \phi \left( {V_i^\tau } \right)} \right)}\limits_{} \text{,} $
其中$ \phi \left( {V_i^\tau } \right) = 1 - \alpha {\left| {V_i^\tau } \right|^\gamma } $. 通过合理地选择$ \alpha $和$ \gamma $,来控制$ \phi \left( {V_i^\tau } \right) $在整个函数中所占的比重. 在重流时,将上一次流式划分的结果(记为$ {\pi _k} = \left\{ {{G_1},{G_2},…,{G_k}} \right\} $)作为已知信息,按照式(6)计算缓冲区中最新的顶点$ {v_{\mathrm{g}}} $应“流”向的子图编号.
$ ind = \mathop {\arg \max }\limits_{i \in \left\{ {1,2,…,k} \right\}} \mathop {\left( {\left| {N\left( {{v_{\mathrm{g}}}} \right) \cap {V_i}} \right| \times \phi \left( {V_i^\tau } \right)} \right)}\limits_{} \text{,} $
其中$ {V_i} $表示上一次流式划分结果中第$ i\left( {i \in \left\{ {1,2,…,k} \right\}} \right) $个子图$ {G_i} $的顶点集,$ V_i^\tau $表示子图$ {G_i} $在本次流式划分中时刻$ \tau $的状态.
4)Hybrid. 在兼顾最优均衡性原则的同时,按照最小化割边比目标实施划分. 给定一种区分顶点度数高低的算法,如设定一个合理的阈值$ \eta $,在时刻$ \tau $,对度数超过该阈值的顶点采用BH决定其“流”向哪个子图,否则采用BWM. 该规则可形式化描述为:
$ {\mathrm{while}}\left( {stream\left( {{v_g}} \right) \ne \varnothing } \right)\left\{ \begin{gathered}{\text{BH}},\;{\mathrm{if}}\;deg\left( {{v_g}} \right) \leqslant \eta , \\{\text{BWM}},\; {\mathrm{if}}\;deg\left( {{v_g}} \right) > \eta . \\ \end{gathered} \right. $
1)实验数据. 我们从SNAP[31]中搜集了wiki-Talk,LiveJournal,Friendster这3个真实数据集,详见表2.
此外,我们还利用图合成工具PaRMAT[32]合成了一系列不同规模且顶点度数分布均服从幂率分布的图数据集,详见表3.
2)对比基准. 选择当前离线划分质量最好的KaMinPar[22]和在线划分质量最好的HeiStream[12],GraSP[25]作为对比基准. 其中,KaMinPar[22]是一种基于共享内存的深层多级图划分算法,除粗化阶段外,在初始划分阶段继续采用多级算法并利用递归二分和直接$ k $路划分计算初始划分方案. HeiStream[12]是一种单加载器-单划分器的缓冲流式划分算法,它按批接收顶点并缓存在缓冲区中,联合批次中的节点和已存在的划分结构构建待划分的图,再利用多级图划分算法实施划分. GraSP[25]是一个采用MPI实现的分布式流式划分算法,其划分规则是FENNEL. 通过使用调整的划分参数对分布式图进行重新流式处理,以实现对大图的快速$ k $路划分.
分布式系统运行在一个由2台DELL Precision 7920 塔式工作站通过网线直接连接而成的工作站机群. 其中,每台工作站都配有2颗英特尔至强金牌6254@3.1GHz CPU、512GB主存以及1TB SSD、8TB HDD. 操作系统版本是Centos 7.9.2009,编译器版本是GCC 9.3,MPI版本是MPICH-3.4.3.
本节设计3组实验,分别讨论所提算法的划分质量与性能. 第1组实验考查划分真实图和合成图的划分质量,评价指标包括均衡性$ \rho $、割边比$ \lambda $;第2组实验考查划分合成图的性能,评价指标包括划分总时间$ \tau $和效率$ \varepsilon $;第3组实验考查缓冲区大小对划分质量的影响,评价指标包括均衡性$ \rho $、割边比$ \lambda $和划分总时间$ \tau $. 在每组实验中,取BWM的参数$ \alpha $和$ \gamma $分别为$ \left\lceil {{n \mathord{\left/ {\vphantom {n k}} \right. } k}} \right\rceil $和1,其中$ n $表示图顶点数,$ k $表示划分路数;取Hybrid的参数$ \eta $为所划分数据集的平均顶点度数;取重流次数为5;每种算法均取5次实验的平均值作为最终结果.
1)划分质量实验. 本实验主要目的是考查所提算法中4条流式启发式规则BH,BB,BWM,Hybrid对2个真实图和6个合成图的划分质量. 不妨取划分进程数$ proc = 8 $、划分路数$ k = 8 $、缓冲区大小$ \omega = 1\;024 $,均衡性和割边比实验结果分别见图3、图4和表4.
不难看出,无论真实图还是合成图,所提算法4条启发式规则BH,BB,BWM,Hybrid的划分质量均明显优于当前最好的在线划分算法GraSP和HeiStream,但在均衡性指标上逊色于当前最好的离线划分算法KaMinPar.
具体来讲,以Hybrid启发式规则为例,割边比指标$ \lambda $较KaMinPar缩减至少36.2个百分点(wiki-Talk数据集),较HeiStream和GraSP分别缩减至少40.4个百分点和18.8个百分点(RMAT-29数据集);以BH为例,其均衡性指标$ \rho $较KaMinPar和HeiStream均增加128.4个百分点(LiveJournal数据集),而GraSP的均衡性相较于KaMinPar和HeiStream均增加358.3个百分点. 但也应看到KaMinPar和HeiStream为保证均衡性,付出了高昂的时间代价. 此外,BH和BB在均衡性指标$ \rho $优于BWM和Hybrid,但在割边比指标$ \lambda $方面却劣于BWM和Hybrid. 这是因为前两者侧重于均衡性,而后两者追求最小化割边比.
由此可见,与不使用缓冲区的GraSP算法相比,本文提出缓冲区机制能够明显提高划分质量,有效缓解冷启动问题. 而使用缓冲区的HeiStream算法表现之所以较本文算法存在一定差距,是因为它将每个已划分子图“池化”一个超级顶点,与缓冲区中各顶点构造一张图,再利用传统多级图划分算法对其实施划分. 该“池化”操作造成划分决策信息损失较大,降低了划分质量.
2)划分性能实验. 本实验主要目的是测试所提4条流式启发式规则BH,BB,BWM,Hybrid的划分性能. 不妨固定图数据为RMAT-22、缓冲区大小$ \omega = 1\,\;024 $、划分路数$ k = 128 $,调整划分进程数$ proc \in \{ 1,2, 4,8,16, 32,64,128 \} $, 记录不同划分算法的总划分时间. 实验结果见图5、图6、图7、表5和表6所示.
从图5、图6和表5可以看出,当$ 1 \lt proc \lt 128 $时,所提算法4条启发式规则BH,BB,BWM,Hybrid在划分总时间指标$ \tau $上显著优于当前最好的离线划分算法KaMinPar和当前最好的在线划分算法GraSP.
具体来讲,不妨以表现最好的BH为例,其较KaMinPar缩减至少80.4个百分点(对应$ proc = 2 $);较HeiStream和GraSP分别缩减至少30.7个百分点和12.9个百分点(对应$ proc = 8 $). 当$ proc = 1 $时,GraSP和所提4条流式启发式规则均蜕化成单加载器-单划分器架构划分算法,它们的划分总时间与HeiStream的差异不明显. 当$ proc = 128 $时,此时进程数已超过CPU物理核心数(80),引发严重的计算资源争用,导致所有划分算法的划分总时间都显著增加. 在效率指标$ \varepsilon $上,无论$ proc $如何变化,所提4条启发式规则与GraSP表现接近,且均显著优于KaMinPar和HeiStream($ proc = 2 $除外). 当proc = 2时效率最高(并行计算资源得到充分利用),而当proc进一步增加时,效率迅速降低,主要是因为并行划分带来的收益不足以弥补并行开销。
从图7和表6可以看出,当划分进程数$ proc \lt 128 $时,所提划分算法的平均划分时间比采用单加载器-单划分器架构的HeiStream算法的划分时间缩减29.8%.
具体来看,HeiStream流式划分算法的数据加载时间占划分总时间的比例平均为30.8%,最高达到35.6%. 而本文所提算法采用多加载器-多划分器架构,其数据加载时间占划分总时间的比例平均为20.1%,最高仅为21.9%. 这表明多加载器-多划分器架构能够有效缓解传统流式划分算法存在的性能瓶颈.
3)缓冲区大小影响力实验. 本实验主要目的是测试缓冲区大小对所提算法划分质量和性能的影响. 不妨以LiveJournal图数据为例,固定划分进程数$ proc = 8 $,调整划分窗口$ \omega \in \left\{128,256,512,1024,2048\right\} $,记录不同划分算法的划分质量和划分总时间,实验结果见表7.
由表7可以看出,所提算法4条启发式规则BH,BB,BWM,Hybrid在不同缓冲区下划分质量变化并不明显,但划分总时间$\tau $随着缓冲区$ \omega $的增加先降低后提高,当$ \omega = 1\,\;024 $时,划分总时间最短. 这是因为当滑动窗口过小时,需要频繁从磁盘中读取图数据流,I/O开销较大. 当$ \omega $进一步增加时,划分总时间逐渐增加,可能的原因是缓冲区顶点排序操作时间增大.
总体来说,如表8所示,在4条启发式规则中,BH和BB更侧重于划分的均衡性,适用于实时性要求高、负载均衡敏感、通信开销不敏感的图计算场景;而BWM和Hybrid兼顾了划分的均衡性和割边比,适用于实时性要求低、负载均衡和通信开销敏感的图计算场景.
本文针对现有图划分算法在划分大图时存在的划分质量和效率难以平衡的问题,提出一种带缓冲区的分布式流式划分算法,通过结合带缓冲区的流式划分算法与分布式划分算法两者的优势,在利用缓冲区辅助信息提高划分质量的同时,借助多加载器-多划分器架构的分布式流式机制提高划分算法性能. 此外,为满足不同划分场景需求,我们设计了4条启发式规则,分别按照最优均衡性、简单高效原则、最大化模块度兼顾均衡性、最小化割边比兼顾均衡性实施划分. 多节点分布式系统上的划分质量与性能实验表明:本文所提算法的划分质量(割边比)比当前最好的在线划分算法改善至少18.8个百分点;多加载器-多划分器架构的设计将图数据加载时间占划分总时间的比例,从单加载器-单划分器架构流式划分算法的平均30.8%降低至平均20.1%,缓解了单加载器-单划分器划分算法存在的性能瓶颈;分布式缓冲机制通过优先划分高度数顶点,有效缓解了冷启动问题.
作者贡献声明:史惠康提出了算法思路和实验方案;王泽胜、胡克坤、董刚完成实验并撰写论文;赵有健提出指导意见并修改论文.

参考文献 引证文献
排序方式:
1
Sakr S, Boifati A, Voigt H, et al. The future is big graphs: A community view on graph processing systems[J]. Communications of the ACM, 2021, 64(9): 62−71
2
杜玉洁,王志刚,王宁,等. 分布式多维大图迭代计算性能优化方法[J]. 计算机研究与发展,2023,60(3):654−675
Du Yujie, Wang Zhigang, Wang Ning, et al. Optimization methods for distributed iterative computing performance over multi-dimensional large graph[J]. Journal of Computer Research and Development, 2023, 60(3): 654−675 (in Chinese)
3
Fan Wenfei. Big graphs: Challenges and opportunities [C]// Proc of the 48th Int Conf on Very Large Data Bases. New York: ACM, 2022: 3782−3797
4
Zhai Xiaomeng, Zhang Hong, Huang Xu, et al. Graph partitioning strategies: One size does not fit all[J]. The Journal of Supercomputing, 2022, 78(17): 19272−19295
5
Dhillon I. Co-clustering documents and words using bipartite spectral graph partitioning [C]//Proc of the 7th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2001: 269−274
6
Karypis G, Kumar V. Multilevel graph partitioning schemes [C]// Proc of the 1995 Int Conf on Parallel Processing. Piscataway, NJ: IEEE, 1995: 113−122
7
Jafari N, Selvitopi O, Aykanat C. Fast shared-memory streaming multilevel graph partitioning[J]. Journal of Parallel and Distributed Computing, 2021, 147(1): 140−151
8
Ji Shengwei, Bu Chenyang, Li Lei, et al. Local graph edge partitioning[J]. ACM Transactions on Intelligent Systems and Technology, 2021, 12(5): 1−25
9
Karypis G, Kumar V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distributed Computing, 1998, 48(1): 96−129
10
Stanton I, Kliot G. Streaming graph partitioning for large distributed graphs [C]// Proc of the 18th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1222−1230
11
Nishimura J, Ugander J. Restreaming graph partitioning: Simple versatile algorithms for advanced balancing [C]//Proc of the 19th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 1106−1114
12
Faraj M, Schulz C. Buffered streaming graph partitioning[J]. ACM Journal of Experimental Algorithmics, 2022, 27(1): 1−26
13
Tsourakakis C, Gkantsidis C, Radunovic B, et al. FENNEL: Streaming graph partitioning for massive scale graphs [C]// Proc of the 7th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2014: 333−342
14
Prabhakaran V, Wu Ming, Weng Xuetian, et al. Managing large graphs on multi-cores with graph awareness [C]// Proc of the 2012 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2012: 41−52
15
Awadelkarim A, Ugander J. Prioritized restreaming algorithms for balanced graph partitioning [C]// Proc of the 26th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2020: 1877−1887
16
Patwary M, Garg S, Kang B. Window-based streaming graph partitioning algorithm [C/OL]// Proc of the 2019 Australasian Computer Science Week Multiconference. New York: ACM, 2019[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_M7eaf008a16906a5f79aM765510178163167&pageSize=25&index=1&searchId=16b73b1aa0124198b09f65fff2d40076&resultsCount=2&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick
17
Faraj M, Schulz C. Buffered streaming graph partitioning[J]. ACM Journal of Experimental Algorithmics, 2022, 27(9): 1−26
18
Hu Kekun, Zeng Guosun, Jiang Huawen, et al. Partitioning big graph with respect to arbitrary proportions in a streaming manner[J]. Future Generation Computer Systems, 2018, 80(1): 1−11
19
Sun Zhipeng, Zeng Guosun, Ding Chunling, et al. A streaming graph partitioning method to achieve high cohesion and equilibrium via multiplayer repeated game[J]. IEEE Transactions on Computational Social Systems, 2022, 11(1): 803−814
20
Pacaci A, Özsu M. Experimental analysis of streaming algorithms for graph partitioning [C]// Proc of the 2019 Int Conf on Management of Data. New York: ACM, 2019: 1375−1392
21
Abbas Z, Kalavri V, Carbone P, et al. Streaming graph partitioning: An experimental study[J]. Proceedings of the VLDB Endowment, 2018, 11(11): 1590−1603
22
Gottesbüren L, Heuer T, Sanders P, et al. Deep multilevel graph partitioning [C]// Proc of the 2021 European Symp on Algorithms. Wadern, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_M6ed4f62317f8aacca4fM60ed1017816328&pageSize=25&index=3&searchId=34b88e32991449758b0b66925964e1eb&resultsCount=4&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick
23
Akhremtsev Y, Sanders P, Schulz C. High-quality shared-memory graph partitioning[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(11): 2710−2722
24
Meyerhenke H, Sanders P, Schulz C. Parallel graph partitioning for complex networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(9): 2625−2638
25
Battaglino C, Pienta R, Vuduc R. GraSP: Distributed streaming graph partitioning [C]// Proc of the 2015 High Performance Graph Mining. Barcelona, Spain: Barcelona Supercomputing Center, 2015[2023-04-21]. https://xueshu.baidu.com/usercenter/paper/show?paperid=9bb30523f8b9a6aa66ddf40fa944ca00&site=xueshu_se
26
Hanai M, Suzumura T, Tan Wenjun, et al. Distributed edge partitioning for trillion-edge graphs[J]. Proceedings of the VLDB Endowment, 2019, 12(13): 2379−2392
27
Mayer C, Mayer R, Tariq M, et al. Adwise: Adaptive window-based streaming edge partitioning for high-speed graph processing [C]// Proc of the 38th IEEE Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2018: 685−695
28
Petroni F, Querzoni L, Daudjee K, et al. Hdrf: Stream-based partitioning for power-law graphs [C]// Proc of the 24th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2015: 243−252
29
Sajjad H, Payberah A, Rahimian F, et al. Boosting vertex-cut partitioning for streaming graphs [C]// Proc of the 5th IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2016[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_4922c18f15887a4b174M79af10178163171&pageSize=25&index=1&searchId=9eb5c2ddc91c49e88880e18ea9b99248&resultsCount=1&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick
30
Çatalyürek Ü, Devine K, Faraj M, et al. More recent advances in (hyper) graph partitioning[J]. ACM Computing Surveys, 2023, 55(12): 1−38
31
Stanford University. SNAP dataset [DB/OL]. [2023-04-21]. http://snap.stanford.edu/data/index.html
32
Khorasani F, Gupta R, Bhuyan L. Scalable SIMD-efficient graph processing on GPUs [C]// Proc of the 24th Int Conf on Parallel Architecture and Compilation. Piscataway, NJ: IEEE, 2015: 39−50
2025年第62卷第7期
106
46
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202330386
  • 接收时间:2023-05-23
  • 首发时间:2026-11-10
  • 出版时间:2025-07-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2023-05-23
  • 修回日期:2025-01-24
  • 录用日期:2025-03-03
基金
作者信息
    1清华大学计算机科学与技术系 北京 100084
    2中国电子技术标准化研究院 北京 100007
    3浪潮电子信息产业股份有限公司 济南 250101

通讯作者:

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

扫描看全文

引用本文
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
关闭全屏