基于SQL的图相似性查询方法

• 作者: 卢卫 杜小勇 王晓黎 赵展浩 黄斐然
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 图编辑距离 图相似查询 PostgreSQL 过滤和验证
• 年，卷（期）: 2018,（3）
• 所属期刊栏目: 基于图结构的大数据分析与管理技术专刊
• 页码范围: 689-702
• 页数: 14页
• 分类号: TP311
• 字数: 9719字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005449

摘要

图作为一种表示复杂信息的数据结构,被广泛应用于社交网络、知识图谱、语义网、生物信息学和化学信息学等领域.随着各领域应用的普及和深入开展,如何管理这些复杂图数据,是目前图数据库技术面临的巨大挑战.图的相似性查询是图数据管理中的热点问题之一,对图查询问题的研究主要包括图的相似性查询等.重点研究基于编辑距离(graph edit distance)的图相似性查询处理问题.首先,通过对目前代表性的问题求解算法分析发现,目前已提出的过滤规则都具有自己的优缺点和适用性.其次,针对已有方法在过滤阶段自身存在的优缺点和适用性的问题,提出一种面向关系型数据库的过滤框架,新的过滤框架可以支持所有已有的过滤规则,从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率.该方法可以最大程度地保留不同过滤规则的优点并克服其缺点,从而对不同查询具有普遍适用性.最后,基于PubChem数据集,通过比较算法在求解查询结果的时间消耗,验证所提出算法的高效性及可扩展性.实验结果表明,所提出的方法优于现有算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王晓黎	厦门大学软件学院	1	2	1.0	1.0