大规模知识图谱的多查询优化问题研究  

Research on multi-query optimization problem in knowledge graph

作　　者：郭欣彤 高宏[1] GUO Xintong;GAO Hong(School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China)

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《智能计算机与应用》2021年第9期119-122,共4页Intelligent Computer and Applications

摘　　要：多查询优化问题是从一组查询中找出公共子结构,将其结果缓存起来,每个查询可以利用缓存结果构建自己的结果。由于知识图谱上的多查询优化是NP-hard问题,现有方法无法在大量查询同时到达时高效地查找公共子结构,也无法保证优化后查询时间一定减少。因此,本文提出了一个新的分布式,基于内存的RDF查询引擎Leon来处理多查询优化问题。Leon使用了基于特征集合的索引和划分方法,具有简单高效、空间占用小的特点。针对现有检测查询之间公共子结构检测算法时间复杂度高的特点,本文提出了一个新颖的多查询优化算法:利用特征集合快速过滤没必要优化的查询,在剩下来的查询中精确、高效地查找公共子结构。实验结果证明:引入多查询优化情形下,时间是基准方法的1/10。Multi-query optimization(MQO)aims to identify common sub-expressions of a set of queries,cache their results,and assemble queries’ final results to avoid redundant computation. Due to the NP-hardness of MQO in knowledge graph,existing methods could not detect common subquery gracefully and cannot assure the runtime reduction after optimization,either. This paper presents Leon,a distributed in-memory knowledge graph query engine,to address the MQO problem. Leon applies a characteristic-set-based indexing and partitioning scheme,which is simple but time-saving. This paper proposes a novel MQO algorithm targeting the high complexity of common sub-expression detection. It uses characteristic sets to filter out the non-promising queries and then discover the high-quality common subquery in the remaining ones. The extensive experiments prove that Leon outperforms10 x faster over the baseline method.

关 键 词：知识图谱 多查询优化 公共子结构检测 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]