基于增量信息索引的子图查询算法

A SUBGRAPH QUERY ALGORITHM BASED ON INCREMENTAL INFORMATION INDEX

当前图数据库中的子图同构查询算法主要是依赖倒排索引,然而处理那些具有庞大数据的数据库和复杂的查询愈发成为挑战。研究目的是设计一个算法,使用新的索引作为查询处理的核心,记录查询图的每一个细小改变,并使用一种特殊的数据结构来维护。先是引出一个索引算法,然后逐渐分析整个索引、查询过程,并利用该算法实现一个系统,最后在不同数据集和查询上进行实验。实验证明了该算法具有良好的时间、空间效率和扩展性。新的索引算法能够支持更大的查询图和更加灵活的查询。通过实现的系统和其他系统的对比实验,验证了算法的有效性。

Currently subgraph isomorphic query algorithms in graph database mainly depend on inverted index. However, the processing ofthose graph databases with huge data and the complicated queries increasingly becomes a challenge. The purpose of our research is to designan algorithm, we used a new index as the core of query processing, recorded every tiny change in query graph, and maintained it with aspecial data structure. First we introduced an index algorithm, and then gradually analysed the whole process of index and query, and usedthe algorithm to have implemented a system, finally we carried out the experiments on different datasets and queries. This algorithm has beenproved with good time and space productivity and scalability. The new index algorithm is able to support greater query graph and more flexiblequery. Through the implemented comparative experiments between this system and other systems, we verified the efficiency of this algorithm.