A Study Of Index Construction For Distance Queries On Big Graphs

With the arrival of the era of Big Data, the size of graphs are becoming more and more bigger. Since traditional algorithms classical for distance query such as Dijkstra,breadth first search(BFS) and Floyd-Warshall's algorithm, are memory-based, none of them are practical. Some online applications require low latency for better user experience,the long running time of classical algorithms make them unsuitable for the real time response.In order to meet the requirement of real time response, the indexes for distance queries on big graphs is proposed. In fact, it is a strategy of space for time. The distance query based on indexes includes two phrases, namely the phrase of constructing indexes and the phrase of distance query. Constructing indexes is an offline procedure, it precomputes the distances between some vertices and stores them as file on the disk. The distance query is an online procedure. Give two query vertices, the distance will be computed through a combination of the previous pre-computed indexes. How to build index to make the preprocessing time as short as possible, the space as small as possible and the corresponding query algorithm as simple as possible is a key factor to solve the problem.We propose a new way aiming at incremental update on dynamic graphs. We focus on the situation that the vertices in don not change while new edges are added into the graph.We update the index which exists with labeling patch. Though this way we can avoid to reconstruct the index and it saves much time.In undirected unweighted dense graphs, especially for strong connection graphs, such as social networks and communication networks, there exists many fully connected subgraphs which also called cliques. We propose a method based on cliques which gathers the distance information in one clique together. Through extensive experiments on various dense graphs in real world, our index can save space compared with other indexes and can speed up querying.