With the rapidly growing availability of vehicle trajectory data, travel costs such as travel time and fuel consumption can be captured accurately as distributions (e.g., travel time distributions) instead of deterministic values (e.g., average travel times). We study a new path finding problem in uncertain road networks, where paths have travel cost distributions. Given a source and a destination, we find optimal, non-dominated paths connecting the source and the destination, where the optimality is defined in terms of the stochastic dominance among cost distributions of paths. We first design an A based framework that utilizes the uncertain graph to obtain the most accurate cost distributions while finding the candidate paths. Next, we propose a three-stage dominance examination method that employs extreme values in each candidate path's cost distribution for early detection of dominated paths, thus reducing the need for expensive distributions convolutions. We conduct extensive experiments using real world road network and trajectory data. The results show that our algorithm outperforms baseline algorithms by up to two orders of magnitude in terms of query response time while achieving the most accurate results.

We define and study Euclidean and spatial network variants of a new path finding problem: given a set of safe zones, find paths that minimize the distance traveled outside the safe zones. In this problem, the entire space with the exception of the safe zones is unsafe, but passable, and it differs from problems that involve unsafe regions to be strictly avoided. As a result, existing algorithms are not effective solutions to the new problem. To solve the Euclidean variant, we devise a transformation of the continuous data space with safe zones into a discrete graph upon which shortest path algorithms apply. A naïve transformation yields a very large graph that is expensive to search. In contrast, our transformation exploits properties of hyperbolas in the Euclidean space to safely eliminate graph edges, thus improving performance without affecting the shortest path results. To solve the spatial network variant, we propose a different graph-to-graph transformation that identifies critical points that serve the same purpose as do the hyperbolas, thus avoiding the creation of extraneous edges. This transformation can be extended to support a weighted version of the problem, where travel in safe zones has non-zero cost. We conduct extensive experiments using both real and synthetic data. The results show that our approaches outperform baseline approaches by more than an order of magnitude in graph construction time, storage space and query response time.