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

Research and application on similarity search algorithm in graph database

作　　者：孟均平[1] 陈莉[1] 马文宁[1] 李华[2] 

机构地区：[1]西北大学信息科学与技术学院,西安710127 [2]西北大学化学分析研究所,西安710069

出　　处：《计算机应用研究》2010年第5期1813-1815,1819,共4页Application Research of Computers

基　　金：国防"973"项目(61374xx)

摘　　要：图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是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.

关 键 词：图查询 图特征 索引 图同构 相似性搜索 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]