Research On Novel Sketch Techniques For Shortest Path Queries Over Dynamic Directed Graphs

In recent years, shortest path query on directed graph has attracted interests of researchers due to multiply shortest path applications on road networks, web networks, social networks and other real-world datasets. The existing algorithm can process shortest path query on undirected graph, but cannot process the shortest path query on directed graph effectively because of the particularity of shortest path query on directed graph. Taking into account those problems raised above, this paper proposes exact and approximate sketch for both shortest path and shortest distance query and incremental computation strategy for the proposed sketch.First, to speed up graph distance sketch construction and exact graph distance query, this paper designs sketch model based on representative vertex triad index (RTI) and spanning tree coding strategy. Since the C-RTI sketch construction requires frequent I/O operation, this paper proposes Q-RTI sketch with new index structure to reduce the I/O cost of sketch construction. After the proof of graph distance query results’correctness on directed graph, this paper designs construction algorithm and query algorithm for both sketches, and extensive experiment evaluation proves the effectiveness of the sketches.Second, this paper proposes new sketch based on discretization landmark with topology level, and returns an error bound result in short time periods. The discretization landmark can reduce the average searching data for individual graph distance query, and topology level can prune some unnecessary query before searching all the sketch data. Since the landmark is not well organized, every query has a lot unnecessary searches; the binary topology landmark (BTL) model is designed to narrow the solution space tree based on the idea of binary search. Then the sketch construction algorithm and query algorithm is proposed and run on real-world datasets and artificial datasets during the experiments. The running time of query on BTL sketch is significantly faster than those existing methods.Third, to reduce the I/O cost during sketch distance query operation and sketch incremental computation, this paper designs a discretization sketch storage formation for Triad set in disk and in memory. This formation also includes a change operation buffer to reduce the average cost of incremental computation, and its effectiveness is proved with amortized analysis in this paper. Extensive experiments are executed to test the efficiency of the I/O effective query algorithm and incremental computation algorithm with this sketch disk model.In summary, considering the challenge of graph distance query technology on directed graph in real applications, this paper proposes a series of sketch techniques such as representative vertex strategy sketch, BTL approximate distance sketch and discretization sketch storage formation for I/O effective query and incremental computation. Those sketches can process various kinds of graph distance query in real application, finish the sketch precomputation with smaller cost and memory, and return the query result with less time.