Searching k-Nearest Neighbor Trajectories on Road Networks

摘要: With the proliferation of mobile devices, massive trajectory data has been generated. Searching trajectories by locations is one fundamental tasks. Previous work such as [3, 6, 9] proposed to answer search. Such typically measures distance between and queries query points GPS trajectories. measurement could be inaccurate because those generated some sampling rate are essentially discrete. To overcome this issue, we treat a sequence line segments compute point segments. Next, index R-tree match each associated inverted lists. After that, propose k-nearest neighbor (KNN) search algorithm on indexing structure. Moreover, cluster merge redundant IDs for higher efficiency. Experimental results validate that method significantly outperforms existing approaches in terms saving storage cost performance.