Efficient Subgraph Matching in Large Graph with Partitioning Scheme
Recently, subgraph matching has been implemented in more and more domains, such as social network and semantic web.An approximated solution for subgraph matching named strong simulation has been put forward.Strong Simulation can preserve the topology of data graphs and find a bounded number of matches, but the complexity further holds a cubic-time, so its yet intractable to deal with large graphs.To solve the problem, this paper focuses on a partition scheme to reduce the search space of subgraph matching algorithm.Firstly, we present a pruning method on data graph based on the connection relationships of nodes and edges in query graph.Secondly, we propose to use a multilevel partitioning algorithm when the subgraphs we get from former step are too large.Thirdly, we propose an algorithm for subgraph matching based on the partitioning scheme, which can preserve the topology of query graph and guarantee the correctness of results.Lastly, we experimentally prove the effectiveness and efficiency of this scheme, both using real-life data and synthetic data.It turns out that our method is quite efficient and the matching results are also satisfactory.
partitioning scheme strong simulation subgraph matching
Xiaofang Xie Zhongwei Li Haiwei Zhang
College of Computer and Control Engineering, Nankai University
国际会议
武汉
英文
28-33
2016-09-23（万方平台首次上网日期，不代表论文的发表时间）