Reverse κ Nearest Neighbor Search over Trajectories

Abstract

GPS enables mobile devices to continuously provide new opportunities to improve our daily lives. For example, the data collected in applications created by Uber or Public Transport Authorities can be used to plan transportation routes, estimate capacities, and proactively identify low coverage areas. In this paper, we study a new kind of query-Reverse κ Nearest Neighbor Search over Trajectories (RκNNT), which can be used for route planning and capacity estimation. Given a set of existing routes DR, a set of passenger transitions DT, and a query route Q, an RκNNTquery returns all transitions that take Q as one of its κ nearest travel routes. To solve the problem, we first develop an index to ..