{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:19:54Z","timestamp":1773825594707,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:p>As large volumes of trajectory data accumulate, simplifying trajectories to reduce storage and querying costs is increasingly studied. Existing proposals face three main problems. First, they require numerous iterations to decide which GPS points to delete. Second, they focus only on the relationships between neighboring points (local information) while neglecting the overall structure (global information), reducing the global similarity between the simplified and original trajectories and making it difficult to maintain consistency in query results, especially for similarity-based queries. Finally, they fail to differentiate the importance of points with similar features, leading to suboptimal selection of points to retain the original trajectory information.<\/jats:p>\n          <jats:p>We propose MLSimp, a novel Mutual Learning query-driven trajectory simplification framework that integrates two distinct models: GNN-TS, based on graph neural networks, and Diff-TS, based on diffusion models. GNN-TS evaluates the importance of a point according to its globality, capturing its correlation with the entire trajectory, and its uniqueness, capturing its differences from neighboring points. It also incorporates attention mechanisms in the GNN layers, enabling simultaneous data integration from all points within the same trajectory and refining representations, thus avoiding iterative processes. Diff-TS generates amplified signals to enable the retention of the most important points at low compression rates. Experiments involving eight baselines on three databases show that MLSimp reduces the simplification time by 42%--70% and improves query accuracy over simplified trajectories by up to 34.6%.<\/jats:p>","DOI":"10.14778\/3705829.3705858","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:21:06Z","timestamp":1740784866000},"page":"453-465","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantifying Point Contributions: A Lightweight Framework for Efficient and Effective Query-Driven Trajectory Simplification"],"prefix":"10.14778","volume":"18","author":[{"given":"Yumeng","family":"Song","sequence":"first","affiliation":[{"name":"Northeastern Univ., China"}]},{"given":"Yu","family":"Gu","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}]},{"given":"Tianyi","family":"Li","sequence":"additional","affiliation":[{"name":"Aalborg Univ., Denmark"}]},{"given":"Yushuai","family":"Li","sequence":"additional","affiliation":[{"name":"Aalborg Univ., Denmark"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg Univ., Denmark"}]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}]}],"member":"320","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150","author":"Beltagy Iz","year":"2020","unstructured":"Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150 (2020)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Fernando Berzal and Nicolf\u00e5s Mat\u00edn. 2002. Data mining: concepts and techniques by Jiawei Han and Micheline Kamber. In SIGMOD. 66--68.","DOI":"10.1145\/565117.565130"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Yanchuan Chang Jianzhong Qi Yuxuan Liang and Egemen Tanin. 2023. Contrastive Trajectory Similarity Learning with Dual-Feature Attention. In ICDE. 2933--2945.","DOI":"10.1109\/ICDE55515.2023.00224"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3665844.3665858"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Lei Chen M Tamer \u00d6zsu and Vincent Oria. 2005. Robust and fast similarity search for moving object trajectories. In SIGMOD. 491--502.","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_2_1_6_1","volume-title":"Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805","author":"Devlin Jacob","year":"2018","unstructured":"Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"David H Douglas and Thomas K Peucker. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: the international journal for geographic information and geovisualization 10 2 (1973) 112--122.","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Ziquan Fang Yuntao Du Xinjun Zhu Danlei Hu Lu Chen Yunjun Gao and Christian S Jensen. 2022. Spatio-temporal trajectory similarity learning in road networks. In KDD. 347--356.","DOI":"10.1145\/3534678.3539375"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Ziquan Fang Changhao He Lu Chen Danlei Hu Qichen Sun Linsen Li and Yunjun Gao. 2023. A lightweight framework for fast trajectory simplification. In ICDE. 2386--2399.","DOI":"10.1109\/ICDE55515.2023.00184"},{"key":"e_1_2_1_10_1","unstructured":"Shansan Gong Mukai Li Jiangtao Feng Zhiyong Wu and Lingpeng Kong. 2023. DiffuSeq: Sequence to Sequence Text Generation with Diffusion Models. In ICLR."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In KDD. 855--864.","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_12_1","volume-title":"LongT5: Efficient text-to-text transformer for long sequences. arXiv preprint arXiv:2112.07916","author":"Guo Mandy","year":"2021","unstructured":"Mandy Guo, Joshua Ainslie, David Uthus, Santiago Ontanon, Jianmo Ni, Yun-Hsuan Sung, and Yinfei Yang. 2021. LongT5: Efficient text-to-text transformer for long sequences. arXiv preprint arXiv:2112.07916 (2021)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3015457"},{"key":"e_1_2_1_14_1","unstructured":"John Edward Hershberger and Jack Snoeyink. 1992. Speeding up the Douglas-Peucker line-simplification algorithm. In SDH. 134--143."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Cuiying Huo Di Jin Yawen Li Dongxiao He Yu-Bin Yang and Lingfei Wu. 2023. T2-GNN: Graph neural networks for graphs with incomplete features and structure via teacher-student distillation. In AAAI. 4339--4346.","DOI":"10.1609\/aaai.v37i4.25553"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Jiawei Jiang Dayan Pan Houxing Ren Xiaohan Jiang Chao Li and Jingyuan Wang. 2023. Self-supervised trajectory representation learning with temporal regularities and travel semantics. In ICDE. 843--855.","DOI":"10.1109\/ICDE55515.2023.00070"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Bingqing Ke Jie Shao and Dongxiang Zhang. 2017. An efficient online approach for direction-preserving trajectory simplification with interval bounds. In MDM. 50--55.","DOI":"10.1109\/MDM.2017.17"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Bingqing Ke Jie Shao Yi Zhang Dongxiang Zhang and Yang Yang. 2016. An online approach for direction-based trajectory compression with error bound guarantee. In AP-Web. 79--91.","DOI":"10.1007\/978-3-319-45814-4_7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Margret Keuper Bjoern Andres and Thomas Brox. 2015. Motion trajectory segmentation via minimum cost multicuts. In ICCB. 3271--3279.","DOI":"10.1109\/ICCV.2015.374"},{"key":"e_1_2_1_20_1","unstructured":"Thomas N Kipf and Max Welling. 2016. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR. 1--14."},{"key":"e_1_2_1_21_1","unstructured":"Lecheng Kong Jiarui Feng Hao Liu Dacheng Tao Yixin Chen and Muhan Zhang. 2023. MAG-GNN: Reinforcement Learning Boosted Graph Neural Network. In NIPS. 12000--12021."},{"key":"e_1_2_1_22_1","unstructured":"Jae-Gil Lee Jiawei Han and Kyu-Young Whang. 2007. Trajectory clustering: a partition-and-group framework. In SIGMOD. 593--604."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450987"},{"key":"e_1_2_1_24_1","volume-title":"Yunjun Gao, and Jilin Hu.","author":"Li Tianyi","year":"2022","unstructured":"Tianyi Li, Lu Chen, Christian S Jensen, Torben Bach Pedersen, Yunjun Gao, and Jilin Hu. 2022. Evolutionary clustering of moving objects. In ICDE. 2399--2411."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384353"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Jiajun Liu Kun Zhao Philipp Sommer Shuo Shang Brano Kusy and Raja Jurdak. 2015. Bounded quadrant system: Error-bounded trajectory compression on the go. In ICDE. 987--998.","DOI":"10.1109\/ICDE.2015.7113350"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598171"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536221"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735466"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10044-008-0133-y"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Nirvana Meratnia and Rolf A de By. 2004. Spatiotemporal compression techniques for moving point objects. In EDBT. 765--782.","DOI":"10.1007\/978-3-540-24741-8_44"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Jonathan Muckell Jeong-Hyon Hwang Vikram Patil Catherine T Lawson Fan Ping and SS Ravi. 2011. SQUISH: an online approach for GPS trajectory compression. In COM.Geo. 1--8.","DOI":"10.1145\/1999320.1999333"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-013-0184-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2436932"},{"key":"e_1_2_1_35_1","unstructured":"Michalis Potamias Kostas Patroumpas and Timos Sellis. 2006. Sampling trajectory streams with spatiotemporal criteria. In SSDBM. 275--284."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.650093"},{"key":"e_1_2_1_37_1","first-page":"46","article-title":"GRASP-UTS: an algorithm for unsupervised trajectory segmentation","volume":"29","author":"J\u00fanior Am\u00edlcar Soares","year":"2015","unstructured":"Am\u00edlcar Soares J\u00fanior, Bruno Neiva Moreno, Val\u00e9ria Ces\u00e5rio Times, Stan Matwin, and Luc\u00eddio dos Anjos Formiga Cabral. 2015. GRASP-UTS: an algorithm for unsupervised trajectory segmentation. IJGIS 29, 1 (2015), 46--68.","journal-title":"IJGIS"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3380643"},{"key":"e_1_2_1_39_1","volume-title":"Attention is all you need. NIPS 30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. NIPS 30 (2017)."},{"key":"e_1_2_1_40_1","unstructured":"Petar Veli\u010dkovi\u0107 Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Li\u00f2 and Yoshua Bengio. 2018. Graph Attention Networks. In ICLR."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611557"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3440207","article-title":"A survey on trajectory data management, analytics, and learning","volume":"54","author":"Wang Sheng","year":"2021","unstructured":"Sheng Wang, Zhifeng Bao, J Shane Culpepper, and Gao Cong. 2021. A survey on trajectory data management, analytics, and learning. CSUR 54, 2 (2021), 1--36.","journal-title":"CSUR"},{"key":"e_1_2_1_43_1","unstructured":"Tongzhou Wang and Phillip Isola. 2020. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In ICML. 9929--9939."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Zheng Wang Cheng Long and Gao Cong. 2021. Trajectory simplification with reinforcement learning. In ICDE. 684--695.","DOI":"10.1109\/ICDE51399.2021.00065"},{"key":"e_1_2_1_45_1","volume-title":"Collectively Simplifying Trajectories in a Database: A Query Accuracy Driven Approach. arXiv preprint arXiv:2311.11204","author":"Wang Zheng","year":"2023","unstructured":"Zheng Wang, Cheng Long, Gao Cong, and Christian S Jensen. 2023. Collectively Simplifying Trajectories in a Database: A Query Accuracy Driven Approach. arXiv preprint arXiv:2311.11204 (2023)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Zheng Wang Cheng Long Gao Cong and Qianru Zhang. 2021. Error-bounded online trajectory simplification with multi-agent reinforcement learning. In KDD. 1758--1768.","DOI":"10.1145\/3447548.3467351"},{"key":"e_1_2_1_47_1","unstructured":"Da Xu Chuanwei Ruan Evren Korpeoglu Sushant Kumar and Kannan Achan. 2020. Inductive Representation Learning on Temporal Graphs. In ICLR. 1--19."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611561"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213885"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Ying Zhang Tao Xiang Timothy M Hospedales and Huchuan Lu. 2018. Deep mutual learning. In CVPR. 4320--4328.","DOI":"10.1109\/CVPR.2018.00454"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Silin Zhou Jing Li Hao Wang Shuo Shang and Peng Han. 2023. GRLSTM: trajectory similarity computation with graph-based residual LSTM. In AAAI. 4972--4980.","DOI":"10.1609\/aaai.v37i4.25624"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3705829.3705858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:27:48Z","timestamp":1740785268000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3705829.3705858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10.14778\/3705829.3705858"],"URL":"https:\/\/doi.org\/10.14778\/3705829.3705858","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2025-02-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}