Database Reference
In-Depth Information
3.7 Probabilistic Path Queries
Last, we review the previous studies related to the probabilistic path queries that will
be discussed in Chapter 8. The existing related work include path queries on proba-
bilistic graphs and on traffic networks. Both problems have been studied extensively.
However, there is no work on extending probabilistic graphs to traffic networks.
3.7.1 Path Queries on Probabilistic Graphs
Frank [136] studied the shortest path queries on probabilistic graphs, where the
weight of each edge is a random variable following certain probability distribution.
The probability distribution of the shortest path is defined. Moreover, a Monte Carlo
simulation method is proposed to approximate the probability distribution of the
shortest path. Loui [137] extended [136] by defining a utility function which speci-
fies the preference among paths. Loui [137] also gave the computationally tractable
formulations of the problem.
The shortest path problem on probabilistic graphs has been studied under differ-
ent constraints. Hassin and Zemel [138] considered computing shortest paths when
the edge weight distributions have a Taylor's series near zero. Wu et al. [139] stud-
ied the shortest path problem with edge weights uniformly and independently dis-
tributed in
. Moreover, Blei and Kaelbling [140] studied the problem of find-
ing the shortest paths in stochastic graphs with partially unknown topologies. The
problem is reduced to a Markov decision problem. Approximation algorithms are
proposed. In [141], the problem of optimal paths in directed random networks is
studied, where the cost of each arc is a real random variable following Gaussian
distribution, and the optimal path is a path that maximizes the expected value of a
utility function. In particular, linear, quadratic, and exponential utility functions are
considered.
Stochastic shortest path search [142, 143, 144] is to find a path between two end
nodes and maximize the probability that the path length does not exceed a given
threshold. It is also referred to as the “stochastic on-time arrival problem (SOTA)”.
SOTA has the same semantics as the WT top-1 queries (a special case of WT top- k
queries discussed in this topic). However, Nikolova et al. [143] only consider some
particular parametric weight distribution (such as the Normal distribution and the
Poisson distribution) and transform the SOTA problem to a quasi-convex maximiza-
tion problem. In addition, there have been other formulations of the optimal routing
problem with probabilistic graphs. Ghosh et al. [145] developed an optimal rout-
ing algorithm that generates an optimal delivery subgraph so that the connectivity
between two end nodes is maximized. Chang and Amir [146] computed the most
reliable path between two end nodes when each edge has a failure probability.
Another related problem is traversing probabilistic graphs. Kahng [147] provided
a nice overview and insights of this problem. Povan and Ball [148] showed that even
[
0
,
1
]
Search WWH ::




Custom Search