Distributed Top-k Subgraph Matching in A Big Graph

Distributed Top-k Subgraph Matching in A Big Graph
复制标题

DOI：
10.1109/bigdata.2018.8622519
复制
发表时间：
2018-12
期刊：
2018 IEEE International Conference on Big Data (Big Data)
影响因子：
--
通讯作者：
Jianliang Gao;Chuqi Lei;Ling Tian;Yuan Ling;Zheng Chen;Bo Song
Jianliang Gao;Chuqi Lei;Ling Tian;Yuan Ling;Zheng Chen;Bo Song
中科院分区：
其他
文献类型：
--
作者：
Jianliang Gao;Chuqi Lei;Ling Tian;Yuan Ling;Zheng Chen;Bo Song

文献摘要

相似文献

子图匹配查询是指找出数据图G中与给定查询图Q匹配的子图。传统的方法计算复杂，不能处理大数据图。本文提出了一种大图上的分布式top-k子图搜索方法。该方法是在单顶点层次上设计的，所有顶点分别获得匹配状态，而不需要全局图信息。因此，它可以很容易地部署在Hadoop这样的分布式平台上。通过对运行时间、消息个数和超步的评估，验证了该方法的有效性和可扩展性。
Subgraph matching query is to find out the sub-graphs of data graph G which match a given query graph Q. Traditional methods can not deal with big data graphs due to their high computational complex. In this paper, we propose a distributed top-k subgraph search method over big graphs. The proposed method is designed at the level of single vertex and all vertices obtain their matching state separately without requiring global graph information. Therefore, it can be easily deployed in distributed platform like Hadoop. The evaluations of running time, number of messages and supersteps show the efficiency and scalability of the proposed method.