Downloaded from: http://www.cs.hku.hk/research/techreps/document/TR-2014-09.pdf
ST-queries include reachability queries (RQ) and shortest distance queries (SDQ). These queries provide answers with probabilistic guarantees. For example, the answer of an RQ tells us the chance that \(s\) can reach \(t\); the SDQ returns the probability distribution of the distance between \(s\) and \(t\).
The main idea is to evaluate the query on \(G(q)\), a weight-distribution probabilistic graph derived from \(G\). Given a probabilistic graph \(G\) and a ST-query \(q\), PTree can generate a probabilistic graph \(G(q)\), which is typically smaller than \(G\) and has fewer possible worlds. Hence, the approach can be considered in some sense as a graph compression algorithm –- but compression of the possible worlds.
In this paper, the authors introduce PTree, a formal indexing framework for probabilistic graphs, and they further present the detailed theoretical and experimental results for three instantiations of PTree (i.e., SPQR tree, FWD, and LIN).
George S. Fishman. 1986. A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness. IEEE Trans. Reliability 35, 2 (1986).
Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. 2011. Distance-Constraint Reachability Computation in Uncertain Graphs. PVLDB 4, 9 (2011).
Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. k-Nearest Neighbors in Uncertain Graphs. PVLDB 3, 1 (2010).
Zhaonian Zou, Hong Gao, and Jianzhong Li. 2010. Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics. In KDD.
Y. Yuan, G. Wang, H. Wang, and L. Chen. Efficient subgraph search over large uncertain graphs. PVLDB, 4(11), 2011.
O. Papapetrou, E. Ioannou, and D. Skoutas. Efficient discovery of frequent subgraph patterns in uncertain graph databases. In EDBT, 2011.
A. Khan, F. Bonchi, A. Gionis, and F. Gullo. Fast reliability search in uncertain graphs. In EDBT, 2014.