Pass-Count-Based Path Query on Big Graph Datasets

Distance and path queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. A new data structure is created for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v. In this paper, a new concept “pass count” is proposed to measure the importance of a vertex in the graph. Based on the pass-count, a special heuristic rule is used to build distance labels for each vertex of the graph, so distance queries and path queries can be processed on those labels exclusively. This method is efficient by avoiding graph traversal, and hence reduces time complexity. A “pass count algorithm” is also presented based on the pass-count of each vertex in the graph, which aims to minimize labels’ size, improve the query processing, and accelerate the construction of the labels. Extensive experiments are conducted to prove the effectiveness and efficiency of the algorithm.