Visible Nearest Neighbor Search for Objects Moving on Consecutive Trajectories

A visible nearest neighbor (VNN) query returns the k nearest objects that are visible to a query point, which is used to support various applications such as route planning, target monitoring, and antenna placement. However, with the proliferation of wireless communications and advances in positioning technology for mobile equipments, efficiently searching for VNN among moving objects are required. While most previous work on VNN query focused on static objects, in this paper, we treats the objects as moving consecutively when indexing them, and study the visible nearest neighbor query for moving objects (MVNN). Assuming that the objects are represented as trajectories given by linear functions of time, we propose a scheme which indexes the moving objects by time-parameterized R-tree (TPR-tree) and obstacles by R-tree. The paper offers four heuristics for visibility and space pruning. New algorithms, Post-pruning and United-pruning, are developed for efficiently solving MVNN queries with all four heuristics. The effectiveness and efficiency of our solutions are verified by extensive experiments over synthetic datasets on real road network.