【作者】 马强；

【导师】 周军锋；

【作者基本信息】 燕山大学 ， 计算机科学与技术， 2017， 硕士

【摘要】 给定有向无环图G,以及图上的任意两点u、v。回答u是否能够到达v的可达性查询是图的基本操作之一。随着现代化信息技术的快速发展,图被广泛应用于生物学、社交网络、语义网络、模式识别等领域,图的可达性查询是图数据管理中的热点问题之一。大量的学者投入精力改进可达性查询算法的效率。但是已存在的可达性查询算法,由于索引占用空间太大、查询效率低下等原因,在面对规模不断增长的数据图时,效率低、扩展性差。本文从以下几个方面对可达性查询问题进行研究。首先,分析现有可达性查询问题,发现已有算法构建索引时间长,索引占用空间大,查询效率低下。其次,本文提出线性时间复杂度的索引构建算法,在拓扑排序的过程中,为每个结点指定相应的索引标签,包含一对互逆的拓扑序号和该结点在生成树上的区间。提出压缩的索引表示方式,索引的空间复杂度为O(n)。提出基于孩子结点的区间扩展策略,对于要扩展的结点u,将其用于覆盖生成树上孩子的区间扩展到图中覆盖出邻居结点的区间,增强了回答肯定性可达查询的能力。再次,在进一步研究结点的拓扑号和区间的关系后,提出基于后代结点的区间扩展策略。对于将要扩展的结点u,把u的后代结点作为扩展目标,进行区间扩展。将其用于覆盖生成树上后代的区间扩展到图中覆盖可达结点的区间,增大了区间扩展的幅度、增强了区间过滤的能力。最后,在25个不同规模的真实数据集上,通过实验从不同角度对算法的性能进行深入比较和分析。实验结果验证了本文算法的高效性和扩展性。更多还原

【Abstract】 Given a directed acyclic graph G,and any two nodes u,v on the graph.Answer whether u can reach v is one of the basic operations of the graph process.With the rapid development of information technology,graphs are widely used in biology,social networks,semantic networks,pattern recognition and other fields.The reachability of graphs is one of the hot issues in graph data management.A large number of scholars have invested in improving the efficiency of the queryability algorithm.In this parper,the reachability query processing method is studied from the following aspects.First of all,analysis of the existing reachability algorithm,found that the existing algorithm take a long time to build a large index and query inefficient.Secondly,this paper proposes an index construction algorithm for linear time complexity.In the process of topology sorting,we assign the corresponding index tags to each node,including a pair of mutually inverted topological numbers and the interval of the nodes in the spanning tree.The spatial complexity of the index is O(n).An interval extension strategy based on the child’s node is proposed.For the node to be extended,it is used to extend the interval of the child on the spanning tree to the interval covering the neighbor nodes in the graph,which enhances the affirmative and reachable query ability.Thirdly,after further studying the relationship between the topology number and the interval of the nodes,an interval extension strategy based on the descendant nodes is proposed.For the node to be extended u,the descendants of u as the expansion of the target.The interval used to cover the descendants of the spanning tree is extended to the range of the reachable nodes in the graph,which increases the amplitude of the interval expansion and enhances the ability of interval filtering.Finally,experiments are carried out on 25 real datasets,and the results are compared and analyzed.The results show that the proposed method is efficient and scalable.更多还原