BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries

Publication Type:
Conference Proceeding
LNCS - Database Systems for Advanced Applications - Part 1, Proceedings of the 16th International Conference on Database Systems for Advanced Applications, 2011, 6587 pp. 434 - 449
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005463OK.pdf293.96 kB
Adobe PDF
Reachability query is a fundamental problem in graph databases. It answers whether or not there exists a path between a source vertex and a destination vertex and is widely used in various applications including road networks, social networks, world wide web and bioinformatics. In some emerging important applications, uncertainties may be inherent in the graphs. For instance, each edge in a graph could be associated with a probability to appear. In this paper, we study the reachability problem over such uncertain graphs in a threshold fashion, namely, to determine if a source vertex could reach a destination vertex with probabilty larger than a user specified probability value t. Finding reachability on uncertain graphs has been proved to be NP-Hard. We first propose novel and effective bounding techniques to obtain the upper bound of reachability probability between the source and destination. If the upper bound fails to prune the query, efficient dynamic Monte Carlo simulation technqiues will be applied to answer the probabilitistic reachability query with an accuracy guarantee. Extensive experiments over real and synthetic datasets are conducted to demonstrate the efficiency and effectiveness of our techniques.
Please use this identifier to cite or link to this item: