图数据库中的相似性搜索算法研究与应用

Research and application on similarity search algorithm in graph database

图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是NP完全问题,传统的高开销搜索的方法已经不能满足复杂图查询的需要;另外,由于图数据库的复杂性和特殊性,已有的优化算法不能直接使用。为了提高图数据库的搜索效率,提出了一种基于索引的相似性搜索算法,通过数据库中的频繁结构建立特征索引,算法可高效准确地滤除大量的非相似图集合,避免了图之间精确匹配即图同构的计算,最后将本算法应用于化学数据库,实验结果证明了该方法的有效性和可行性。

Similarity search of graph database is a significant research subject. The graph similarity match belongs to the category of decision problem of graph isomorphism. That is NP complete problem. The traditional high-consuming approach has not been able to meet the contemporary needs of complex graph search. Additionally, because of the complexity and specificity of graph database, the existing optimization algorithm can not be applied directly to this field. Therefore, it is necessary to explore a more advanced graph similarity algorithm. This paper proposed a novel similarity search algorithm, which was based on index. That was, establishing a feature index though frequent structure in database. The algorithm could filter a large number of non-similar data sets effectively and accurately, thus avoiding the calculation of exact match. Finally, applied the algorithm to the chemical database. The experimental result demonstrates that the approach is effective and feasible.