Efficient Similar Subtrajectory Search Using Deep Reinforcement Learning
Discover how deep reinforcement learning enhances the efficiency and effectiveness of finding similar subtrajectories in trajectory data. The study introduces the SimSub problem, trajectory similarity measurements, and algorithms like Prefix-Suffix Search. Learn about Reinforcement Learning-based Search with Skipping for improved trajectory analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Efficient and Effective Similar Subtrajectory Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning Search with Deep Reinforcement Learning Zheng Wang, Cheng Long, Gao Cong, Yiding Liu Nanyang Technological University 1
Trajectory Data Trajectory Data Player trajectory Vehicle trajectory Pedestrian trajectory Animal trajectory 2
Similar Trajectory Search Similar Trajectory Search T1 and T2 are dissimilar to Tq T1 has a portion that is similar to Tq 3
SimSub SimSub Problem Problem SimSub problem: return a portion of a data trajectory (i.e., a subtrajectory), which is the most similar to a query trajectory Tq is a query trajectory and T is a data trajectory: Return T[2:4] = <p2, p3, p4> General framework using any similarity measurement 4
Trajectory Similarity Measurement Trajectory Similarity Measurement DTW and Frechet: Pairwise matching Quadratic time complexity t2vec: Data-driven (representation learning) Linear time complexity 5
Algorithms Algorithms Linear time (t2vec) 6
Prefix Prefix- -Suffix Search (PSS) Suffix Search (PSS) Split at current point P_i, it updates the splitting index to i+1 max(sim_prefix, sim_suffix) > sim_best Splitting index Point Prefix Suffix Split BEST P1 T[1,1] T[1,5] Yes 2 T[1,5] P2 T[2,2] T[2,5] Yes 3 T[2,2] P3 T[3,3] T[3,5] No 3 T[2,2] No P4 T[3,4] T[4,5] 3 T[2,2] P5 T[3,5] T[5,5] No 3 T[2,2] Output: BEST=T[2,2] max(sim_prefix, sim_suffix) <= sim_best 7
Algorithms Algorithms Linear time (t2vec) 8
Reinforcement Learning based Search with Skipping (RLS Reinforcement Learning based Search with Skipping (RLS- -Skip) Skip) Split at current point P_i, it updates the splitting index to i+1 Splitting as an MDP: State: S = (sim_best, sim_prefix, sim_suffix) Action: Split, No-split, Skip Transition: from S to S Reward: S .sim_best - S.sim_best Skip next point State Splitting index Point Action BEST (best, prefix, suffix) Deep-Q- Network ( ,T[1,1],T[1,5]) Split 2 T[1,5] P1 P2 (T[1,5],T[2,2],T[2,5]) Skip 2 T[2,2] - P3 - - - P4 Split (T[2,2],T[2,4],T[4,5]) 5 T[2,4] P5 (T[2,2],T[5,5],T[5,5]) No-split 5 T[2,4] Output: BEST=T[2,4] 9
Experimental Setup Experimental Setup Datasets Compared Methods Experiments Performance metrics Porto (1.7M) Proposed algorithms Approximate ratio Effectiveness Harbin (1.2M) UCR [1] Mean rank Sports (0.2M) Spring [2] Random-S Relative rank Running time Efficiency [1] T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh. Searching and mining trillions of time series subsequences under dynamic time warping. SIGKDD 2012. [2] Y. Sakurai, C. Faloutsos, and M. Yamamuro. Stream monitoring under the time warping distance. ICDE 2007. 10
Effectiveness Results Effectiveness Results RLS achieves the best effectiveness 11
Efficiency Results Efficiency Results RLS-Skip achieves the best efficiency 4 10 SizeS RLS RLS-Skip Time without Index (s) ExactS PSS 3 10 POS POS-D 2 10 0.4 0.8 1.2 1.6 2.0 Data Size (million) 12
Parameter Study Parameter Study Skipping Steps k for RLS Skipping Steps k for RLS- -Skip Skip 13
Comparison with UCR, Spring and Random Comparison with UCR, Spring and Random- -S S UCR and Spring Random-S 14
Conclusion Conclusion + + Problem Algorithms Experiments Experiments Performance metrics Approximate ratio Effectiveness Mean rank Relative rank Efficiency Running time 15
Q & A Q & A THANKS FOR WATCHING 16
