Efficient and effective similar subtrajectory search with deep reinforcement learning
Similar trajectory search is a fundamental problem and has been well studied over the past two decades. However, the similar subtrajectory search (SimSub) problem, aiming to return a portion of a trajectory (i.e., a subtrajectory), which is the most similar to a query trajectory, has been mostly dis...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/148162 |
| _version_ | 1826113018564444160 |
|---|---|
| author | Wang, Zheng Long, Cheng Cong, Gao Liu, Yiding |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Wang, Zheng Long, Cheng Cong, Gao Liu, Yiding |
| author_sort | Wang, Zheng |
| collection | NTU |
| description | Similar trajectory search is a fundamental problem and has been well studied over the past two decades. However, the similar subtrajectory search (SimSub) problem, aiming to return a portion of a trajectory (i.e., a subtrajectory), which is the most similar to a query trajectory, has been mostly disregarded despite that it could capture trajectory similarity in a finer-grained way and many applications take subtrajectories as basic units for analysis. In this paper, we study the SimSub problem and develop a suite of algorithms including both exact and approximate ones. Among those approximate algorithms, two that are based on deep reinforcement learning stand out and outperform those nonlearning based algorithms in terms of effectiveness and ef-ficiency. We conduct experiments on real-world trajectory datasets, which verify the effectiveness and efficiency of the proposed algorithms. |
| first_indexed | 2024-10-01T03:16:37Z |
| format | Conference Paper |
| id | ntu-10356/148162 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:16:37Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1481622021-05-06T01:26:50Z Efficient and effective similar subtrajectory search with deep reinforcement learning Wang, Zheng Long, Cheng Cong, Gao Liu, Yiding School of Computer Science and Engineering Proceedings of the VLDB Endowment (VLDB 2020) Engineering::Computer science and engineering::Information systems::Database management Similar Subtrajectory Search Deep Learning Similar trajectory search is a fundamental problem and has been well studied over the past two decades. However, the similar subtrajectory search (SimSub) problem, aiming to return a portion of a trajectory (i.e., a subtrajectory), which is the most similar to a query trajectory, has been mostly disregarded despite that it could capture trajectory similarity in a finer-grained way and many applications take subtrajectories as basic units for analysis. In this paper, we study the SimSub problem and develop a suite of algorithms including both exact and approximate ones. Among those approximate algorithms, two that are based on deep reinforcement learning stand out and outperform those nonlearning based algorithms in terms of effectiveness and ef-ficiency. We conduct experiments on real-world trajectory datasets, which verify the effectiveness and efficiency of the proposed algorithms. Ministry of Education (MOE) Nanyang Technological University Published version This research is supported by the Nanyang Technological University Start-UP Grant from the College of Engineering under Grant M4082302 and by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG20/19 (S)). 2021-05-06T01:26:50Z 2021-05-06T01:26:50Z 2020 Conference Paper Wang, Z., Long, C., Cong, G. & Liu, Y. (2020). Efficient and effective similar subtrajectory search with deep reinforcement learning. Proceedings of the VLDB Endowment (VLDB 2020), 13, 2312-2325. https://dx.doi.org/10.14778/3407790.3407827 https://hdl.handle.net/10356/148162 10.14778/3407790.3407827 2-s2.0-85091066065 13 2312 2325 en START-UP GRANT, RG20/19 (S) © 2020 The Author(s) (published by VLDB Endowment). This work is licensed under the Creative Commons Attribution Non Commercial No Derivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/byncnd/4.0/. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. application/pdf |
| spellingShingle | Engineering::Computer science and engineering::Information systems::Database management Similar Subtrajectory Search Deep Learning Wang, Zheng Long, Cheng Cong, Gao Liu, Yiding Efficient and effective similar subtrajectory search with deep reinforcement learning |
| title | Efficient and effective similar subtrajectory search with deep reinforcement learning |
| title_full | Efficient and effective similar subtrajectory search with deep reinforcement learning |
| title_fullStr | Efficient and effective similar subtrajectory search with deep reinforcement learning |
| title_full_unstemmed | Efficient and effective similar subtrajectory search with deep reinforcement learning |
| title_short | Efficient and effective similar subtrajectory search with deep reinforcement learning |
| title_sort | efficient and effective similar subtrajectory search with deep reinforcement learning |
| topic | Engineering::Computer science and engineering::Information systems::Database management Similar Subtrajectory Search Deep Learning |
| url | https://hdl.handle.net/10356/148162 |
| work_keys_str_mv | AT wangzheng efficientandeffectivesimilarsubtrajectorysearchwithdeepreinforcementlearning AT longcheng efficientandeffectivesimilarsubtrajectorysearchwithdeepreinforcementlearning AT conggao efficientandeffectivesimilarsubtrajectorysearchwithdeepreinforcementlearning AT liuyiding efficientandeffectivesimilarsubtrajectorysearchwithdeepreinforcementlearning |