Propabilistic graphs may be:
where each edge is augmented with a probability value, which indicates the chance that the edge exists.
where each edge is associated with a probability distribution of weight values.
Evaluation of ST-queries is hard (#P-hard). You have to create all possible (non-probabilistic) words that correspond to the probabilistic graph and evaluate the query in each one.
To improve the efficiency sampling is employed, where possible worlds with high existential probabilities are extracted.
Can we take advantage of Ehab’s work to compute the samples?