Path Analysis Algorithms On Graph Data

Hop-constrained s-t simple path(k-st path)enumeration is a fundamental problem in graph databases and plays an important role in many real-world applications,especially for dynamic environments.Given a dynamic graph G with edge updates,a source-target pair s-t,and a hop constraint k,the k-st path enumeration aims to list all simple paths from s to t such that the length is up to k,and then continuously report the updated paths resulting from edge updates.Although the k-st path enumeration has been well studied,we observe that the existing solutions are all designed for static graphs and can't handle the dynamic graph efficiently.The existing works for static graphs suffer either inefficient query processing or high result updating cost when processing dynamic graphs.To address these challenges,we propose a partial path-based index structure and efficient enumeration algorithm based on the index.We also provide several well-designed techniques to efficiently maintain the index and report affected results when the graph updates.Comprehensive experiments show our proposed CPE_update algorithm outperforms the baselines by up to 4 orders of magnitude on dynamic graphs.The experiment results also show that,even on static graphs,our proposed CPE_startup algorithm archives similar performance to the state-of-the-art static method.Furthermore,for some scenarios where the number of path results is so large that the enumeration of paths is meaningless and hard to be computed in a real time manner,this paper proposes a strategy of using path counting instead of path enumeration.For the path counting query,we develop an efficient algorithm to compute the number of paths without enumerating all paths.The experimental results show that using path counting can save more than 90%of the computing time.