ProbTree: A Query-Efficient Representation of Probabilistic Graphs
Silviu Maniu, Cheng, Reynold, Senellart, Pierre · The HKU Scholars Hub (University of Hong Kong) · 2014
Information in many applications, such as mobile wireless systems, social networks, and road networks, is captured by graphs, in many cases uncertain.We study the problem of querying a probabilistic graph; in particular, we examine "source-to-target" queries, such as computing the shortest path between two vertices.Evaluating ST-queries over probabilistic graphs is #P-hard, as it requires examining an exponential number of "possible worlds".Existing solutions to the ST-query problem, which sample possible worlds, have two downsides: (i) many samples are needed for reasonable accuracy, and (ii) a possible world can be very large.To tackle these issues, we study the ProbTree, a data structure that stores a succinct representation of the probabilistic graph.Existing ST-query solutions are executed on top of this structure, with the number of samples and possible world sizes reduced.