作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2023, Vol. 49 ›› Issue (1): 73-81. doi: 10.19678/j.issn.1000-3428.0063640

• 人工智能与模式识别 • 上一篇    下一篇

基于图结构特征采样数据摘要的联邦知识图谱查询

高峰1,2,3,4, 李秋1,2,3,4, 顾进广1,2,3,4   

  1. 1. 武汉科技大学 计算机科学与技术学院, 武汉 430065;
    2. 湖北省智能信息处理与实时工业系统重点实验室, 武汉 430065;
    3. 武汉科技大学 大数据科学与工程研究院, 武汉 430065;
    4. 国家新闻出版署富媒体数字出版内容组织与知识服务重点实验室, 北京 100083
  • 收稿日期:2021-12-28 修回日期:2022-02-01 发布日期:2022-03-22
  • 作者简介:高峰(1986-),男,讲师、博士,主研方向为知识图谱、智能信息处理、语义网;李秋,硕士研究生;顾进广,教授、博士。
  • 基金资助:
    国家科技创新2030—“新一代人工智能”重大项目(2020AAA0108500);国家自然科学基金(U1836118);富媒体数字出版内容组织与知识服务重点实验室开放基金(ZD2021-11/01)。

Federated Knowledge Graph Query Based on Graph Structure Feature Sampling Data Summary

GAO Feng1,2,3,4, LI Qiu1,2,3,4, GU Jinguang1,2,3,4   

  1. 1. School of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan 430065, China;
    2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System, Wuhan 430065, China;
    3. Big Data Science and Engineering Research Institute, Wuhan University of Science and Technology, Wuhan 430065, China;
    4. Key Laboratory of Rich Media Digital Publishing Content Organization and Knowledge Service, National Press and Publication Administration, Beijing 100083, China
  • Received:2021-12-28 Revised:2022-02-01 Published:2022-03-22

摘要: 联邦SPARQL查询是通过构建查询计划来指导查询执行,数据摘要索引文件捕获了RDF数据集的结构和语义信息,对查询计划生成过程中子查询基数评估至关重要。现有的数据摘要生成方法需要远程遍历每个数据源的完整数据,该过程成本消耗较高,且在大部分环境中联邦查询无法完成对大数据集的统计工作。为在减少数据摘要索引文件生成时间和内存开销的同时捕获尽可能真实的计数信息,考虑主语和谓语的分布偏差,提出利用样图生成原始图近似数据摘要的方法。使用对RDF图出度特征加权的采样方法获取原始图的典型样图,通过改进的映射函数将样图中的信息映射到原始图上,从而生成原始图的近似数据摘要。实验结果表明,该方法相比于基线方法至少节省了70%的数据摘要索引文件生成时间,并且仅采样0.5%的原始图生成的近似数据摘要即可在查询正确率上与基线方法保持高度一致。

关键词: 数据摘要, 数据源索引, RDF图采样, 联邦查询, 查询性能

Abstract: The federated system processes SPARQL queries by constructing an effective query plan to guide query execution.The data summary index file captures the structure and semantic information of Resource Description Framework(RDF) datasets, essential for the cardinality evaluation of subqueries during query plan generation.Existing data summary generation methods need to traverse the complete data of each source remotely, which consumes a high cost.In most environments, the federated query cannot complete the statistics of large datasets.This study proposes a method for generating the approximate data summary of the original graph based on the sample graph to solve this defect.The aim is to capture the actual count information as much as possible while reducing the generation time and memory overhead of the data summary index file. Specifically, this method first uses the sampling method of weighting the degree feature of the RDF graph to obtain the typical sample of the original graph.Next, the improved mapping function reflects the information in the sample graph to the original graph to generate the approximate data summary of the original graph. During this process, the distribution deviation of the subject and predicate is considered in this method.The experimental results show that the proposed method saves at least 70% of the generation time of the data summary index file compared with the Baseline method.In addition, the approximate data summary generated only from 0.5% of the original graph is highly consistent with the Baseline method in query accuracy.

Key words: data summary, data source index, RDF graph sampling, federation query, query performance

中图分类号: