Abstract: A basic approach of investigating the relationship between two vertices on the uncertain graph is to enumerate all paths between them.To solve the problem of inadequate pruning and redundant computation in the state-of-the-art algorithms,this paper proposes an pruning and index based algorithm,PIEnum,whose target is to enumerate simple paths from a source vertex s to a target vertex t where the length of each path is no more than a given hop constraint k and the probability of each path is no less than a given probability threshold γ.For an input query,it firstly excludes the unpromising vertices to reduce the search space.Then it builds an online light-weight index to avoid repeated pruning examinations during the enumeration.Finally,it develops an efficient approach to prune invalid search branches during the enumeration.To further improve the performance on dense graphs,it implements PIEnum⁺ based on the Join paradigm.The comprehensive experimental results on 10 real-life graphs show that PIEnum improves the overall performance by at least 10 times compared to the state-of-the-art algorithms.

Key words: Graph, Uncertain graph, Path enumeration, Pruning, Index