Computing a Subtrajectory Cluster from c-Packed Trajectories
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 807 KB, PDF-dokument
We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. At least one subtrajectory must be of length l or longer. A trajectory T is c-packed if the intersection of T and any ball B with radius r is at most c · r in length. Previous results by Gudmundsson and Wong [24] established an Ω(n3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n3 log2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c2n/ε2) log(c/ε) log(n/ε)) time complexity.
Originalsprog | Engelsk |
---|---|
Titel | 34th International Symposium on Algorithms and Computation, ISAAC 2023 |
Redaktører | Satoru Iwata, Satoru Iwata, Naonori Kakimura |
Antal sider | 15 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2023 |
Artikelnummer | 34 |
ISBN (Elektronisk) | 9783959772891 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 34th International Symposium on Algorithms and Computation, ISAAC 2023 - Kyoto, Japan Varighed: 3 dec. 2023 → 6 dec. 2023 |
Konference
Konference | 34th International Symposium on Algorithms and Computation, ISAAC 2023 |
---|---|
Land | Japan |
By | Kyoto |
Periode | 03/12/2023 → 06/12/2023 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 283 |
ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding Joachim Gudmundsson: Funded by the Australian Government through the Australian Research Council DP180102870.
Publisher Copyright:
© Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0.
ID: 390893259