Network Voronoi Diagram on uncertain objects for nearest neighbor queries

In the past decade, probabilistic nearest neighbor (PNN) query processing has received significant research attention due to the development of mobile smart terminals and the advances in wireless communication technologies. However, to the best of our knowledge, most of the existing PNN-oriented studies are aimed at the Euclidean space and cannot be readily extended to road networks. This paper takes the first step toward processing PNN queries in road Networks (NPNN). We first present an efficient method to construct Network Voronoi Diagram on Uncertain objects (UNVD), in which we first find the possible NNs of all the vertices, and then compute the u-edges as well as their corresponding possible NNs. Next, to process NPNN queries, we first present a computational method to calculate the probabilities for each possible nearest object, and then propose two data structures, namely gIndex and qIndex, to index the u-edges in UNVD. Finally, we evaluate the performance of our NPNN query processing methods via extensive experiments on both real road networks and synthetic 2-dimensional grid networks. Experimental results demonstrate the effectiveness and efficiency of our methods in terms of I/O cost and query time.