Efficient Indexing And Querying System For Large-Scale Graphs

Answering widest path queries,shortest path distance queries,and reachability queries are fundamental problem of graph query.There exists a wide range of applications such as transportation planning and network routing for them.The traditional solution for these query problems to compute directly on the original graph by using online algorithms,such as a variant of Dijkstra or BFS.Such a solution has a long computation time which grows linearly with the graph size.Thus it cannot be used for applications with low latency demand.The other extreme thought is to pre-compute all query results and store them in an inmemory index.Thus every query can be answered instantly.However,the pre-processing time and index size are quadratic and not acceptable for large graphs.Therefore,it is challenging to design an algorithm for these query problems with high time and space efficiency.To address these issues,based on a classical 2-hop labeling structure,the system stores a partial query results in an in-memory index,and supports exact query with extreme low latency.The system proposes a novel pruned widest path labeling algorithm,which obtains good balance between query time,index size,and indexing time.The system also supports the shortest path and reachability query on large-scale graphs by indexing algorithms.Experimental results demonstrate that all three algorithms of system perform well on graphs with hundreds of millions of vertices and edges,with comparable query time to previous methods.The average query time is in the microsecond level,six orders of magnitude faster than previous methods.The algorithms of this system can scale to graphs with hundreds of millions of edges and vertices,which have good scalability.