Discovery of probabilistic nearest neighbors in traffic-aware spatial networks

Travel planning and recommendation have received significant attention in recent years. In this light, we study a novel problem of discovering probabilistic nearest neighbors and planning the corresponding travel routes in traffic-aware spatial networks (TANN queries) to avoid potential time delay/traffic congestions. We propose and study four novel probabilistic TANN queries. Thereinto two queries target at minimizing the travel time, including a congestion-probability threshold query, and a time-delay threshold query, while another two travel-time threshold queries target at minimizing the potential time delay/traffic congestion. We believe that TANN queries are useful in many real applications, such as discovering nearby points of interest and planning convenient travel routes for users, and location based services in general. The TANN queries are challenged by two difficulties: (1) how to define probabilistic metrics for nearest neighbor queries in traffic-aware spatial networks, and (2) how to process these TANN queries efficiently under different query settings. To overcome these challenges, we define a series of new probabilistic metrics and develop four efficient algorithms to compute the TANN queries. The performances of TANN queries are verified by extensive experiments on real and synthetic spatial data.