An Efficient Algorithm for Maximum Trajectory Coverage Query With Approximation Guarantee
METADATA ONLY
Loading...
Author / Producer
Date
2022-12
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
In this paper, we study the $k$ Maximum Trajectory Coverage Query, which aims to find $k$ routes in a public transport system that can serve the maximum number of users with given journey trajectories. In existing studies, they only consider independent service that includes no transfers, but overlooks the aggregative service that includes transfer of multiple routes, resulting in inferior results. In our study, we consider both independent and aggregative services, which can help provide more meaningful results. However, the problem is NP-hard and non-submodular. To address this problem, we propose a greedy algorithm that iteratively selects the route with the maximum marginal gain considering both independent and aggregative services, and show that it outperforms the competitor by up to 60% in terms of accuracy. Since the problem is non-submodular, the greedy algorithm typically does not provide any approximation guarantee. By a mild assumption, we show that our proposed solution provides a constant approximation with respect to the optimal one. Moreover, since we need to consider both the independent and aggregative service, our greedy algorithm becomes more complicated and brings additional time overheads. To overcome such a deficiency, we further accelerate our solution using several heuristics and present an efficient method for spatially associating trajectories and routes. Extensive experiments on real-world datasets demonstrate that our optimisation brings up to an order of magnitude speedup and even outperforms existing solutions (that consider no aggregative service) by 2-3 times.
Permanent link
Publication status
published
External links
Editor
Book title
Volume
23 (12)
Pages / Article No.
24031 - 24043
Publisher
IEEE
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Spatial database; Check-in trajectory; Maximum coverage; Location-based applications