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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An Efficient Algorithm for Maximum Trajectory Coverage Query With Approximation Guarantee


    Contributors:
    He, Dan (author) / Zhou, Thomas (author) / Zhou, Xiaofang (author) / Kim, Jiwon (author)

    Published in:

    Publication date :

    2022-12-01


    Size :

    1182620 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Maximum Coverage Representative Skyline

    Søholm, Malene / Chester, Sean / Assent, Ira | DataCite | 2016


    Multiple structure recovery with maximum coverage

    Magri, L. / Fusiello, A. | British Library Online Contents | 2018



    VALUATION GUARANTEE DEVICE, VALUATION GUARANTEE METHOD, AND PROGRAM

    NISHIDA GIICHI | European Patent Office | 2021

    Free access

    Approach trajectory guidance for maximum concealment

    Warner, David N., Jr. | NTRS | 1988