Reverse k Nearest Neighbor Search over Trajectories (Extended Abstract)

We study a new kind of query - a Reverse k Nearest Neighbor Search over Trajectories (RkNNT), which can be used for route planning and capacity estimation in the transportation field. Given a set of existing routes DR, a set of passenger transitions DT, and a query route Q, an RkNNT query returns al...

Full description

Saved in:
Bibliographic Details
Main Authors: Sheng Wang, Zhifeng Bao, Culpepper, J. Shane, Sellis, Timos, Gao Cong
Format: Conference Proceeding
Language:English
Subjects:
capacity prediction
route planning
Trajectory database
transit network
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study a new kind of query - a Reverse k Nearest Neighbor Search over Trajectories (RkNNT), which can be used for route planning and capacity estimation in the transportation field. Given a set of existing routes DR, a set of passenger transitions DT, and a query route Q, an RkNNT query returns all transitions that take Q as one of its k nearest travel routes. We develop an index to handle dynamic trajectory updates, so that the most up-to-date transition data is available for answering an RkNNT query using a filter-refine processing framework. Further, an application of using RkNNT to plan the optimal route in bus networks, namely MaxRkNNT, is proposed and studied. Experiments on real datasets demonstrate the efficiency and scalability of our approaches. In the future, the RkNNT can be extended to applied to the traffic prediction.
ISSN:2375-026X
DOI:10.1109/ICDE.2018.00250