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

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

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