Visible Nearest Neighbor Search For Moving Objects

As the development of internet, especially the evolution of mobile net, the volume of spatial data is growing exponentially. Spatial location-based information connects the disparate data to make critical decisions which can be used in a variety of appli-cations. The wide proliferation of wireless communication technology promotes the development of processing moving objects in the field of Spatial.In this paper we introduce the notion of visible nearest neighbor search for moving objects(MVNN) which is based on the concept of nearest neighbor query for moving objects, and we also propose an effective solution to process it.Given a data set P, an obstacle set O, a query point q, and a time interval T, a MVNN query retrieves the points in P nearest to q among those visible to q during T.Although the NN query and its variants have been extensively studied in the lit-erature, query for visible nearest moving objects has never been addressed. Assuming that the objects are represented as points given by linear functions of time, we propose a scheme which indexes the moving objects by a time-parameterized R-tree (TPR-tree) and the obstacles in a R-tree. We present algorithms based on this scheme for solv-ing visible kNN queries efficiently and the main idea is to traverse the TPR-tree in a best-first order and prune the search space in spatial and visual clusters in a branch-and-bound fashion. In addition, the algorithms are extended to support retrieval of the visible k nearest moving objects, namely MVkNN.Furthermore, we propose a framework of processing MVNN query, simulate syn-thetic datasets on real road network, implement the prototype and demonstrate the effectiveness and efficiency of the proposed scheme by a large number of experiments.