Research On Shortest Path Query Method For Large-Scale Graphs

As the basic data structure of describing the relationship among real-world entities, graphs are widely used in complex network analysis, the emerging field of bioinformatics, geography navigation, logistics planning and so on. With the era of big data, the size of graph data grows rapidly, and at the same time, the topology of graph data has become more complex, which results in the analysis of the large-scale graph data facing enormous challenges. The shortest path query is one of the core content in graph theory, so a lot of problems in the real world can be converted to this method as the solution. However, with the increase of the scale of network, the classic method of the shortest path query can not meet the queries of large-scale graph, which means we need to find a more effective and valid shortest path query according to various needs of applications has a certain research significance.In this paper, after the intensive studies of shortest path query in large-scale graph, we found that preprocessing techniques are generally used as the important way of improving the efficiency of the query, which includes the precision shortest path query and the approximate shortest path query in large-scale graph. After preprocessing in large-scale graph, the response time of the query algorithm is a constant result. Therefore, at first, based on the idea of preprocessing, this paper proposed the approximate shortest path query method, which is querying shortest path with the key vertexes to guide in large-scale graph. In the method, it selects K vertexes in graphs as the key vertex set, and it only needs to calculate and store the shortest path of the key vertex in preprocessing, which can effectively reduce the amount of redundant data storage, at the same time improve the efficiency of preprocessing. In the process of query, the shortest path is estimated based on the key vertex, so the shortest path between the source and the destination point can be converted to three sections:the shortest path between source and key vertex, the shortest path between the key vertexes, and the shortest path between key vertex and the destination vertex, which narrows the scope of the search area and effectively improves the query efficiency of the shortest path. However key vertex set as the "hub" vertexes in the graph, the shortest path query is estimated through the key vertex using the upper bound manner, this method there will be some errors, but approximate shortest path query can be verified through experiments within an acceptable error in large-scale graph.In order to meet the needs of the precise query and improve the efficiency of preprocessing, this paper proposes shortest path query based on tree decomposition and label cover. In the method, firstly, the large-scale graph is mapped into the tree structure by tree decomposition; Secondly, it needs to create minimized label set to cover the tree structure, and then optimize the tree structure and the structure of the distance label to effectively reduce the storage of redundant data and narrow the traversal range of vertexes, which increases the efficiency of preprocessing and reduces the overall cost of preprocessing; Finally, based on the index structure created in preprocessing, it only needs a simple traversal of the tree structure to complete the query, which further improves the efficiency of query.Finally, this paper by experiments tests the two proposed methods and contrasts with the existing shortest path queries. After analyzing the experimental results, it verified the two shortest path queries proposed in this paper have better efficiency of preprocessing and query.