计算机科学
交叉口(航空)
枚举
相交图
独立集
合并(版本控制)
组合数学
算法
图形
数学
理论计算机科学
折线图
并行计算
工程类
航空航天工程
作者
Weiguo Zheng,Yifan Yang,Chengzhi Piao
标识
DOI:10.1145/3447548.3467219
摘要
Given two sets of vertices Sa and Sb of a graph, computing their common vertices, namely set intersection, is one primitive operation in many graph algorithms such as triangle counting, maximal clique enumeration, and subgraph matching. Thus, accelerating set intersections is beneficial to these algorithms. In the paper, we propose a novel reducing-merging framework for set intersections over graphs rather than intersecting the two sets directly. In the reducing phase, the vertices that cannot fall into the intersection are screened out by applying the range reduction. Based on the truncated subsets, the intersection can be easily obtained using the classic merging algorithm. To optimize the range codes that sketch the vertices, we formulate the problem of range code optimization and prove its NP-hardness. We develop efficient yet effective algorithms for two typical scenarios global intersection and local intersection. Moreover, we present a novel two-level merging algorithm to enhance the performance. The results of extensive experiments over real graphs show that our approach can achieve significant speedups compared to the merge-based algorithm.
科研通智能强力驱动
Strongly Powered by AbleSci AI