计算机应用 ›› 2017, Vol. 37 ›› Issue (1): 48-53.DOI: 10.11772/j.issn.1001-9081.2017.01.0048

• 2016年全国开放式分布与并行计算学术年会(DPCS2016)论文 • 上一篇    下一篇

基于双层索引结构的起源图查询方法

许国艳, 罗章璇, 宋健, 吕鑫   

  1. 河海大学 计算机与信息学院, 南京 211100
  • 收稿日期:2016-07-20 修回日期:2016-08-06 出版日期:2017-01-10 发布日期:2017-01-09
  • 通讯作者: 许国艳
  • 作者简介:许国艳(1971-),女,内蒙古赤峰人,副教授,博士,主要研究方向:大数据、数据起源;罗章璇(1989-),男,安徽滁州人,硕士研究生,主要研究方向:数据起源管理;宋健(1991-),男,江苏盐城人,硕士研究生,主要研究方向:大数据管理;吕鑫(1983-),男,江苏南京人,讲师,博士,主要研究方向:密码学、网络信息安全。
  • 基金资助:
    国家863计划项目(2013BAB06B04);中国华能集团公司总部科技项目(HNKJ13-H17-04);江苏省自然科学基金资助项目(BK20130852);水利部公益性行业科研专项经费项目(201501007)。

Provenance graph query method based on double layer index structure

XU Guoyan, LUO Zhangxuan, SONG Jian, LYU Xin   

  1. College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China
  • Received:2016-07-20 Revised:2016-08-06 Online:2017-01-10 Published:2017-01-09
  • Supported by:
    This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2013BAB06B04), the Technology Project of China Huaneng Group Headquarters (HNKJ13-H17-04), the Natural Science Foundation of Jiangsu Province (BK20130852), the Special Fund for Public Welfare Industry of the Ministry of Water Resources of China (201501007).

摘要: 为解决现有的起源图查询效率低和资源占用率高的问题,考虑起源信息和数据本身之间的关联关系以及起源信息内部结构特点,提出了一种基于双层索引结构的起源图查询方法。首先,面向起源图查询,提出了一种包括基于词典表全局索引和基于位图局部索引的双层索引结构,全局索引用于查询起源图所存储的服务器节点,局部索引用于对全局索引查询到的服务器节点细化查询;然后,基于双层索引结构,设计了一种起源图查询方法,针对6种选择索引和3种join链接索引实现了查询算法。实验结果表明,所提方法既提高了查询效率,又降低了内存资源的浪费。

关键词: 起源图, 双层索引结构, 词典表, 位图

Abstract: To solve the problem of low query efficiency and high resource occupancy of the existing provenance graph query system, and consider the internal structure characteristics of provenance information, the relationship between the provenance of information and the data itself, a provenance graph query method based on double layer index structure was proposed. Firstly, for provenance graph query, a double layer index structure including global index based on dictionary table and local index based on bitmap was established. Global index was used to query the server nodes stored in provenance graph, and local index was for refining the query inside one server node. Secondly, based on the dual index structure, a provenance graph query method was designed, in view of the six kinds of selection index and three kinds of join link index. The experimental results show that the proposed method not only improves the query efficiency, but also reduces the waste of memory resources.

Key words: provenance graph, double layer index structure, dictionary table, bitmap

中图分类号: