电子学报 ›› 2015, Vol. 43 ›› Issue (8): 1531-1537.DOI: 10.3969/j.issn.0372-2112.2015.08.010

• 学术论文 • 上一篇    下一篇

RDF图的Top-k最短路径查询

章登义, 吴文李, 欧阳黜霏   

  1. 武汉大学计算机学院, 湖北武汉 430072
  • 收稿日期:2014-04-15 修回日期:2014-09-27 出版日期:2015-08-25 发布日期:2015-08-25
  • 通讯作者: 吴文李
  • 作者简介:章登义 男,1965年出生于湖北省荆州市.现为武汉大学计算机学院教授、博士生导师. E-mail:dyzhangwhu@163.com欧阳黜霏 男,1988年出生于湖北省荆州市.现为武汉大学博士研究生,从事数据库、数据挖掘方面的研究工作. E-mail:whuxiaoouou@whu.edu.cn

Top-k Shortest-Path Query on RDF Graphs

ZHANG Deng-yi, WU Wen-li, OUYANG Chu-fei   

  1. School of Computer, Wuhan University, Wuhan, Hubei 430072, China
  • Received:2014-04-15 Revised:2014-09-27 Online:2015-08-25 Published:2015-08-25

摘要:

最短路径查询是图数据管理与复杂关系挖掘的基本操作之一.本文针对资源描述框架图上的top-k最短路径查询,构造基于组件的索引,并在该索引的基础上实现查询的响应.查询优化阶段,针对查询效率问题,提出频繁路径以及结构剪枝策略,并给出有效性证明.实验表明,本文方法准确返回top-k最短路径并提高92%的查询速率.索引构造时间相比已有方法,提高约56%.同时,索引所占空间仅为原始数据大小的1~1.2倍.

关键词: 资源描述框架, 最短路径查询, 图数据库, top-k, 查询处理

Abstract:

Finding the shortest path in a graph is a fundamental operation that allows complex relationships discovering in a graph database.This paper considers top-k shortest-path queries on RDF(Resource Description Framework) graphs.To solve this problem, we provide a component-based index for path queries and present an approach to answer the top-k shortest-path query.To efficiently process queries, we propose frequent path strategy and structural pruning.For frequent path strategy, we precompute the top-k shortest-paths between frequent entities obtained from the frequent paths.For the structural pruning, we find out the termination condition for queries by considering the structural information of component-based index and derive two lemmas to guide this pruning mechanism.Experiments results show that the query runtime is improved by 92% using our answering approach and the construction time of our index for RDF graphs is speeded up by 56%.Meanwhile, the size of this index is only 0~0.2 times larger than that of the raw graphs.

Key words: resource description framework(RDF) graph, shortest path query, graph database, top-k, query processing

中图分类号: