Probabilistic Shortest Time Queries Over Uncertain Road Networks
Chen, Yaqing · ScholarWorks @ UTRGV (The University of Texas Rio Grande Valley) · 2014
In many real applications such as location-based services (LBS), map utilities, trip planning, and transportation systems, it is very useful and important to provide query services over spatial road networks. Nowadays we can easily obtain rich traffic information such as the speeds of vehicles on roads. However, due to the inaccuracy of devices or integration in consistencies, the traffic data (i.e., speeds) are often imprecise and uncertain. In this paper, we model road networks by uncertain graphs, which contain edges that are associated with probabilistic velocities. We formalize the problem of probabilistic shortest time query, and we propose time bound pruning and probabilistic bound pruning to filter out false alarms. Moreover, we design offline pre-computation to facilitate PSTQ processing.