Graph Similarity Join with K-Hop Tree Indexing

• 作者: Chen Ye Hong Gao Hongzhi Wang Yue Wang
• 来源期刊: 国际计算机前沿大会会议论文集
• 学科: 社会科学
• 关键词: GRAPH SIMILARITY JOIN EDIT distance constraint k-hop tree based INDEXING structure conservation boundary filtering
• 年，卷（期）: 2015,（1）
• 页码范围: 13-14
• 页数: 2页
• 分类号: C5

摘要

Graph similarity join has become imperative for integrating noisy and inconsistent data from multiple data sources. The edit distance is commonly used to measure the similarity between graphs. To accelerate the similarity join based on graph edit distance, in the paper, we make use of a preprocessing strategy to remove the mismatching graph pairs with significant differences. Then a novel method of building indexes for each graph is proposed by grouping the nodes which can be reached in k hops for each key node with structure conservation, which is the k-hop-tree based indexing method. Experiments on real and synthetic graph databases also confirm that our method can achieve good join quality in graph similarity join. Besides, the join process can be finished in polynomial time.