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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An Efficient Algorithm for Maximum Trajectory Coverage Query With Approximation Guarantee


    Beteiligte:
    He, Dan (Autor:in) / Zhou, Thomas (Autor:in) / Zhou, Xiaofang (Autor:in) / Kim, Jiwon (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    2022-12-01


    Format / Umfang :

    1182620 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    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 | Europäisches Patentamt | 2021

    Freier Zugriff