基于索引的并行图可达性查询算法

Parallel Graph Reachability Queries Algorithm Based on Index

随着图数据库(Graph Database)的不断发展,各种应用程序中都存在着大规模图数据,使得图的可达性查询算法受到了广泛的关注.然而由于其空间消耗与查询效率难以平衡,图可达性查询算法面临着严峻的挑战.基于串行运算的传统图查询算法,很难发挥现有多核心处理器的计算性能.针对上述问题,提出了一种基于双链表的索引,称为2-lists.该索引表由两部分组成,其中一部分存储图数据的信息,另一部分辅助索引,实现顶点的随机访问.基于该索引,提出了一种并行化深度优先搜索算法(Parallel Depth-First Search,PDFS).该算法利用多线程技术,并为每个线程分配独立的存储空间.通过对线程工作量的监督,为线程的指定缓冲区分配指定数量的任务,进而完成负载平衡.在斯坦福SNAP(Stanford Network Analysis Platform,SNAP)实验室的公开数据集上的实验结果表明,2-lists索引占用的空间更小,基于2-lists的并行化深度优先搜索算法的表现更好.

With the development of graph database technology,reachability query algorithms on graph have received widespread attention to deal with large-scale graph data.However,it is difficult to balance the space consumption and query efficiency,so graph reachability queries algorithms are facing challenges.Traditional graph query algorithms based on serial operations are difficult to use the computing performance of existing multi-core processors.To solve above problems,an index termed 2-lists based on double linked lists is proposed.2-lists index consists of two parts,one of which aims to store the information of the graph data,the other to realize random access to the vertices.Based on the index,a parallel depth-first search algorithm is proposed.The algorithm uses multi-threading technique and allocates independent storage space for each thread.It allocates a specified number of tasks to the specified buffer of the thread by supervising thread workload to complete load balancing.The experimental results on the public data set of the Stanford SNAP(Stanford Network Analysis Platform,SNAP)laboratory show that the 2-lists index takes up less space consumption,and the parallel depth-first search algorithm based on 2-lists achieves better performance.