新闻中心

科研动态 | 深圳计算科学研究院1篇论文被国际顶刊IEEE TKDE 2021录用

发布时间:2021-08-23 阅读量:

日前,深圳计算科学研究院(以下简称“研究院”)1篇论文《Graph Algorithms with Partition Transparency》被国际顶级期刊IEEE TKDE正式收录。此次发表的论文开创性地提出了分区透明度的概念,解决了图算法不能在不同的分区下正常工作的难点问题,并能够进一步提升图分区算法的计算速度,彰显了研究院在图计算领域全面领先的科研实力。

1629716198466

目前,为了处理现实生活中的大型图,我们常常需要对分区图进行并行计算。于是,人们提出了各种图分区算法,包括边切割、点切割,以及混合分区。然而,针对特定图分区方法开发的图算法不能在其他图分区下正常工作,导致如需切换到其他图分区方法,可能不得不重写算法。

为了解决这一问题,研究院科研团队及其合作者开创性地提出了分区透明度的概念,这样图算法就能够在不同的分区下正常工作而无需更改,同时还能进一步提升混合分区算法的计算速度。实验证明:

(1)以图为中心模型和以点为中心模型的透明算法在边切割、点切割和混合分区下都能正确工作,不需要任何修改。

(2)在混合分区下的透明算法,比在边切割和点切割下的算法平均快2.3-21.2倍;同样的,比在边切割和点切割下的定制算法平均快2.8和1.6倍。

(3)即使所有算法都在点切割或边切割的情况下运行,透明算法与为单个分区量身定制的算法之间的性能差距也很小,不超过5.8%。

(4)在混合分区下,透明算法具有较好的扩展性,还能较快地处理大型图。当处理器数量n从32变为160时,平均快2.5倍。透明的WCC(weakly connected component)和PR(PageRank)算法在使用90个处理器对具有500M顶点和6B边的图进行计算时,平均花费66.5秒。


论文链接:

https://ieeexplore.ieee.org/document/9495146


数读研究院科研成果:

截至2021年8月23日,研究院共发表/录用高水平论文54篇,其中CCF A类44篇;申请专利/PCT共26项,授权发明专利3项。科研成果比肩全球任何一支大数据学术团队。