{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T01:12:15Z","timestamp":1781917935295,"version":"3.54.5"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T00:00:00Z","timestamp":1632787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program","doi-asserted-by":"crossref","award":["2016YFB1000103"],"award-info":[{"award-number":["2016YFB1000103"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61925203"],"award-info":[{"award-number":["61925203"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100011347","name":"SKLSDE","doi-asserted-by":"crossref","award":["2020ZX-31"],"award-info":[{"award-number":["2020ZX-31"]}],"id":[{"id":"10.13039\/501100011347","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>Nowadays, various sensors are collecting, storing, and transmitting tremendous trajectory data, and it is well known that the storage, network bandwidth, and computing resources could be heavily wasted if raw trajectory data is directly adopted. Line simplification algorithms are effective approaches to attacking this issue by compressing a trajectory to a set of continuous line segments, and are commonly used in practice. In this article, we first classify the error bounded line simplification algorithms into different categories and review each category of algorithms. We then study the data aging problem of line simplification algorithms and distance metrics from the views of aging friendliness and aging errors. Finally, we present a systematic experimental evaluation of representative error bounded line simplification algorithms, including both compression optimal and sub-optimal methods, in terms of commonly adopted perpendicular Euclidean, synchronous Euclidean, and direction-aware distances. Using real-life trajectory datasets, we systematically evaluate and analyze the performance (compression ratio, average error, running time, aging friendliness, and query friendliness) of error bounded line simplification algorithms with respect to distance metrics, trajectory sizes, and error bounds. Our study provides a full picture of error bounded line simplification algorithms, which leads to guidelines on how to choose appropriate algorithms and distance metrics for practical applications.<\/jats:p>","DOI":"10.1145\/3474373","type":"journal-article","created":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T20:52:15Z","timestamp":1632862335000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Error Bounded Line Simplification Algorithms for Trajectory Compression: An Experimental Evaluation"],"prefix":"10.1145","volume":"46","author":[{"given":"Xuelian","family":"Lin","sequence":"first","affiliation":[{"name":"State Key Laboratory of Software Development Environment, Beihang University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuai","family":"Ma","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Software Development Environment, Beihang University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiahao","family":"Jiang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Software Development Environment, Beihang University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanchen","family":"Hou","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Software Development Environment, Beihang University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tianyu","family":"Wo","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Software Development Environment, Beihang University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0096-5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_12"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0163-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2017.01.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646335.687965"},{"key":"e_1_2_1_6_1","first-page":"95","article-title":"Space-efficient algorithms for approximating polygonal curves in two dimensional space","volume":"13","author":"Chen Danny Z.","year":"2002","unstructured":"Danny Z. Chen and Ovidiu Daescu . 2002 . Space-efficient algorithms for approximating polygonal curves in two dimensional space . IJCGA 13 , 2 (2002), 95 \u2013 111 . Danny Z. Chen and Ovidiu Daescu. 2002. Space-efficient algorithms for approximating polygonal curves in two dimensional space. IJCGA 13, 2 (2002), 95\u2013111.","journal-title":"IJCGA"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2012.14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2012.2186146"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629890.1629898"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.80"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.07.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2811302"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687645"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/cgip.1994.1021"},{"key":"e_1_2_1_16_1","first-page":"28","article-title":"Trajectory data reduction in wireless sensor networks","volume":"1","author":"Ghica Oliviu","year":"2010","unstructured":"Oliviu Ghica , Goce Trajcevski , Ouri Wolfson , Ugo Buy , Peter Scheuermann , Fan Zhou , and Dennis Vaccaro . 2010 . Trajectory data reduction in wireless sensor networks . IJNGC 1 , 1 (2010), 28 \u2013 51 . Oliviu Ghica, Goce Trajcevski, Ouri Wolfson, Ugo Buy, Peter Scheuermann, Fan Zhou, and Dennis Vaccaro. 2010. Trajectory data reduction in wireless sensor networks. IJNGC 1, 1 (2010), 28\u201351.","journal-title":"IJNGC"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0216-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3015457"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Geoinformation and Cartography","volume-title":"Map projections in planetary cartography","author":"Hargitai Henrik","unstructured":"Henrik Hargitai , Jue Wang , Philip J. Stooke , Irina Karachevtseva , Akos Kereszturi , and M\u00e1ty\u00e1s Gede . 2017. Map projections in planetary cartography . In Lecture Notes in Geoinformation and Cartography . Springer International Publishing . Henrik Hargitai, Jue Wang, Philip J. Stooke, Irina Karachevtseva, Akos Kereszturi, and M\u00e1ty\u00e1s Gede. 2017. Map projections in planetary cartography. In Lecture Notes in Geoinformation and Cartography. Springer International Publishing."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0262-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(86)80027-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2017.17"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2013.01.071"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.657889"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00102"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0237-7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384353"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00575-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067432"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113350"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598171"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536221"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735466"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113282"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125634"},{"key":"e_1_2_1_37_1","first-page":"61","article-title":"Trajectory data mining: A review of methods and applications","volume":"13","author":"Mazimpaka Jean Damascene","year":"2016","unstructured":"Jean Damascene Mazimpaka and Sabine Timpf . 2016 . Trajectory data mining: A review of methods and applications . Journal of Spatial Information Science 13 (2016), 61 \u2013 99 . Jean Damascene Mazimpaka and Sabine Timpf. 2016. Trajectory data mining: A review of methods and applications. Journal of Spatial Information Science 13 (2016), 61\u201399.","journal-title":"Journal of Spatial Information Science"},{"key":"e_1_2_1_38_1","first-page":"87","article-title":"On polygonal chain approximation","volume":"6","author":"Melkman Avraham","year":"1988","unstructured":"Avraham Melkman and Joseph O\u2019Rourke . 1988 . On polygonal chain approximation . Machine Intelligence and Pattern Recognition 6 (1988), 87 \u2013 95 . Avraham Melkman and Joseph O\u2019Rourke. 1988. On polygonal chain approximation. Machine Intelligence and Pattern Recognition 6 (1988), 87\u201395.","journal-title":"Machine Intelligence and Pattern Recognition"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 9th International Conference on Extending Database Technology (EDBT\u201904)","author":"Meratnia Nirvana","unstructured":"Nirvana Meratnia and Rolf A . de By. 2004. Spatiotemporal compression techniques for moving point objects . In Proceedings of the 9th International Conference on Extending Database Technology (EDBT\u201904) . Nirvana Meratnia and Rolf A. de By. 2004. Spatiotemporal compression techniques for moving point objects. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT\u201904)."},{"key":"e_1_2_1_40_1","unstructured":"Rohit Metha and V. K. Mehta. 1999. The Principles of Physics. S Chand.  Rohit Metha and V. K. Mehta. 1999. The Principles of Physics. S Chand."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869847"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999320.1999333"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-013-0184-0"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2436932"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358758"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.224041"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0208-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2006.45"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2007.05.002"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(72)80017-0"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 1973 International Computing Symposium.","author":"Reumann K.","year":"1974","unstructured":"K. Reumann and A.P.M Witkam . 1974 . Optimizing curve segmentation in computer graphics . In Proceedings of the 1973 International Computing Symposium. K. Reumann and A.P.M Witkam. 1974. Optimizing curve segmentation in computer graphics. In Proceedings of the 1973 International Computing Symposium."},{"key":"e_1_2_1_52_1","first-page":"3","article-title":"Semantic trajectory compression: Representing urban movement in a nutshell","volume":"4","author":"Richter Kai-Florian","year":"2012","unstructured":"Kai-Florian Richter , Falko Schmid , and Patrick Laube . 2012 . Semantic trajectory compression: Representing urban movement in a nutshell . JOSIS 4 , 1 (2012), 3 \u2013 30 . Kai-Florian Richter, Falko Schmid, and Patrick Laube. 2012. Semantic trajectory compression: Representing urban movement in a nutshell. JOSIS 4, 1 (2012), 3\u201330.","journal-title":"JOSIS"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02982-0_30"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1179\/000870406X93490"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(80)90031-X"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732940"},{"key":"e_1_2_1_57_1","volume-title":"International Symposium on Robotics and Automation.","author":"Toussaint G. T.","year":"1985","unstructured":"G. T. Toussaint . 1985 . On the complexity of approximating polygonal curves in the plane . In International Symposium on Robotics and Automation. G. T. Toussaint. 1985. On the complexity of approximating polygonal curves in the plane. In International Symposium on Robotics and Automation."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM\u201916)","author":"Trajcevski Goce","year":"2016","unstructured":"Goce Trajcevski . 2016 . Compression of spatio-temporal data \u2013 Advanced seminar . In Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM\u201916) . Goce Trajcevski. 2016. Compression of spatio-temporal data \u2013 Advanced seminar. In Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM\u201916)."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140104.1140110"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016028.1016030"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/648260.753066"},{"key":"e_1_2_1_62_1","volume-title":"Geographical Information Systems: Principles, Techniques, Management And Applications","author":"Weibel Robert","unstructured":"Robert Weibel and Genevieve Dutton . 1999. Generalising spatial data and dealing with multiple representations . In Geographical Information Systems: Principles, Techniques, Management And Applications ( 2 nd edition), Cambridge, Geoinformation International, P. A. Longley, M. F. Goodchild, D. J. Maquire, and R. W. Rhind (Eds) . 125\u2013155. Robert Weibel and Genevieve Dutton. 1999. Generalising spatial data and dealing with multiple representations. In Geographical Information Systems: Principles, Techniques, Management And Applications (2nd edition), Cambridge, Geoinformation International, P. A. Longley, M. F. Goodchild, D. J. Maquire, and R. W. Rhind (Eds). 125\u2013155.","edition":"2"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(78)90055-2"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(81)90047-2"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0355-0"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213885"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.oceaneng.2018.12.019"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of AutoCarto 13","author":"Zhao Zhiyuan","year":"1997","unstructured":"Zhiyuan Zhao and Alan Saalfeld . 1997 . Linear-time sleeve-fitting polyline simplification algorithms . In Proceedings of AutoCarto 13 . Zhiyuan Zhao and Alan Saalfeld. 1997. Linear-time sleeve-fitting polyline simplification algorithms. In Proceedings of AutoCarto 13."},{"key":"e_1_2_1_69_1","first-page":"32","article-title":"GeoLife: A collaborative social networking service among user, location and trajectory","volume":"33","author":"Zheng Yu","year":"2010","unstructured":"Yu Zheng , Xing Xie , and Wei-Ying Ma . 2010 . GeoLife: A collaborative social networking service among user, location and trajectory . IEEE Data Engineering Bulletin 33 , 2 (2010), 32 \u2013 39 . Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Engineering Bulletin 33, 2 (2010), 32\u201339.","journal-title":"IEEE Data Engineering Bulletin"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474373","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3474373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:26Z","timestamp":1750188626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,28]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3474373"],"URL":"https:\/\/doi.org\/10.1145\/3474373","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,28]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}