{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:07:17Z","timestamp":1759133237003,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MASTER","award":["777695"],"award-info":[{"award-number":["777695"]}]},{"name":"Track8Know","award":["780754"],"award-info":[{"award-number":["780754"]}]},{"name":"Operational Program Competitiveness, Entrepreneurship, and Innovation"},{"name":"European Regional Development Fund of the European Union and Greek national funds"},{"name":"EU Horizon 2020 R8I Programme"},{"name":"datACRON","award":["687591"],"award-info":[{"award-number":["687591"]}]},{"name":"RESEARCH-CREATE-INNOVATE","award":["T1EDK-3268"],"award-info":[{"award-number":["T1EDK-3268"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            Joining trajectory datasets is a significant operation in mobility data analytics and the cornerstone of various methods that aim to extract knowledge out of them. In the era of Big Data, the production of mobility data has become massive and, consequently, performing such an operation in a centralized way is not feasible. In this article, we address the problem of\n            <jats:italic>Distributed Subtrajectory Join<\/jats:italic>\n            processing by utilizing the MapReduce programming model. Compared to traditional trajectory join queries, this problem is even more challenging since the goal is to retrieve all the \u201cmaximal\u201d portions of trajectories that are \u201csimilar.\u201d We propose three solutions: (i) a well-designed basic solution, coined\n            <jats:italic>DTJb<\/jats:italic>\n            ; (ii) a solution that uses a preprocessing step that repartitions the data, labeled\n            <jats:italic>DTJr<\/jats:italic>\n            ; and (iii) a solution that, additionally, employs an indexing scheme, named\n            <jats:italic>DTJi<\/jats:italic>\n            . In our experimental study, we utilize a 56GB dataset of real trajectories from the maritime domain, which, to the best of our knowledge, is the largest real dataset used for experimentation in the literature of trajectory data management. The results show that\n            <jats:italic>DTJi<\/jats:italic>\n            performs up to 16\u00d7 faster compared with\n            <jats:italic>DTJb<\/jats:italic>\n            , 10\u00d7 faster than\n            <jats:italic>DTJr<\/jats:italic>\n            , and 3\u00d7 faster than the closest related state-of-the-art algorithm.\n          <\/jats:p>","DOI":"10.1145\/3373642","type":"journal-article","created":{"date-parts":[[2020,2,28]],"date-time":"2020-02-28T12:40:48Z","timestamp":1582893648000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Distributed Subtrajectory Join on Massive Datasets"],"prefix":"10.1145","volume":"6","author":[{"given":"Panagiotis","family":"Tampakis","sequence":"first","affiliation":[{"name":"University of Piraeus, Piraeus, Greece"}]},{"given":"Christos","family":"Doulkeridis","sequence":"additional","affiliation":[{"name":"University of Piraeus, Piraeus, Greece"}]},{"given":"Nikos","family":"Pelekis","sequence":"additional","affiliation":[{"name":"University of Piraeus, Piraeus, Greece"}]},{"given":"Yannis","family":"Theodoridis","sequence":"additional","affiliation":[{"name":"University of Piraeus, Piraeus, Greece"}]}],"member":"320","published-online":{"date-parts":[[2020,2,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Kyle Fox Kamesh Munagala Abhinandan Nath Jiangwei Pan and Erin Taylor. 2018. Subtrajectory clustering: Models and algorithms. In PODS. 75--87.  Pankaj K. Agarwal Kyle Fox Kamesh Munagala Abhinandan Nath Jiangwei Pan and Erin Taylor. 2018. Subtrajectory clustering: Models and algorithms. In PODS. 75--87.","DOI":"10.1145\/3196959.3196972"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536227"},{"key":"e_1_2_1_3_1","volume-title":"Tsotras","author":"Bakalov Petko","year":"2005","unstructured":"Petko Bakalov , Marios Hadjieleftheriou , Eamonn J. Keogh , and Vassilis J . Tsotras . 2005 . Efficient trajectory joins using symbolic representations. In Proceedings of MDM. 86--93. Petko Bakalov, Marios Hadjieleftheriou, Eamonn J. Keogh, and Vassilis J. Tsotras. 2005. Efficient trajectory joins using symbolic representations. In Proceedings of MDM. 86--93."},{"key":"e_1_2_1_4_1","volume-title":"Tsotras","author":"Bakalov Petko","year":"2005","unstructured":"Petko Bakalov , Marios Hadjieleftheriou , and Vassilis J . Tsotras . 2005 . Time relaxed spatiotemporal trajectory joins. In Proceedings of ACM-GIS. 182--191. Petko Bakalov, Marios Hadjieleftheriou, and Vassilis J. Tsotras. 2005. Time relaxed spatiotemporal trajectory joins. In Proceedings of ACM-GIS. 182--191."},{"key":"e_1_2_1_5_1","volume-title":"Tsotras","author":"Bakalov Petko","year":"2006","unstructured":"Petko Bakalov and Vassilis J . Tsotras . 2006 . Continuous spatiotemporal trajectory joins. In GSN. 109--128. Petko Bakalov and Vassilis J. Tsotras. 2006. Continuous spatiotemporal trajectory joins. In GSN. 109--128."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.05.004"},{"key":"e_1_2_1_7_1","volume-title":"Patel","author":"Chen Yun","year":"2009","unstructured":"Yun Chen and Jignesh M . Patel . 2009 . Design and evaluation of trajectory join algorithms. In Proceedings of SIGSPATIAL. 266--275. Yun Chen and Jignesh M. Patel. 2009. Design and evaluation of trajectory join algorithms. In Proceedings of SIGSPATIAL. 266--275."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629175.1629198"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Hui Ding Goce Trajcevski and Peter Scheuermann. 2008. Efficient similarity join of large sets of moving object trajectories. In TIME. 79--87.  Hui Ding Goce Trajcevski and Peter Scheuermann. 2008. Efficient similarity join of large sets of moving object trajectories. In TIME. 79--87.","DOI":"10.1109\/TIME.2008.25"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0319-9"},{"key":"e_1_2_1_11_1","volume-title":"Mokbel","author":"Eldawy Ahmed","year":"2015","unstructured":"Ahmed Eldawy and Mohamed F . Mokbel . 2015 . SpatialHadoop: A MapReduce framework for spatial data. In Proceedings of ICDE. 1352--1363. Ahmed Eldawy and Mohamed F. Mokbel. 2015. SpatialHadoop: A MapReduce framework for spatial data. In Proceedings of ICDE. 1352--1363."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2492561"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816701"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44039-2_15"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of 14th ACM International Symposium on Geographic Information Systems, ACM-GIS 2006","author":"Gudmundsson Joachim","year":"2006","unstructured":"Joachim Gudmundsson and Marc J . van Kreveld. 2006. Computing longest duration flocks in trajectory data . In Proceedings of 14th ACM International Symposium on Geographic Information Systems, ACM-GIS 2006 , November 10-11, 2006 , Arlington, Virginia. 35--42. Joachim Gudmundsson and Marc J. van Kreveld. 2006. Computing longest duration flocks in trajectory data. In Proceedings of 14th ACM International Symposium on Geographic Information Systems, ACM-GIS 2006, November 10-11, 2006, Arlington, Virginia. 35--42."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366104"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453971"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920934"},{"key":"e_1_2_1_19_1","volume-title":"Ni","author":"Luo Wuman","year":"2012","unstructured":"Wuman Luo , Haoyu Tan , Huajian Mao , and Lionel M . Ni . 2012 . Efficient similarity joins on massive high-dimensional datasets using MapReduce. In Proceedings of MDM. 1--10. Wuman Luo, Haoyu Tan, Huajian Mao, and Lionel M. Ni. 2012. Efficient similarity joins on massive high-dimensional datasets using MapReduce. In Proceedings of MDM. 1--10."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.39"},{"key":"e_1_2_1_21_1","volume-title":"DeWitt","author":"Patel Jignesh M.","year":"1996","unstructured":"Jignesh M. Patel and David J . DeWitt . 1996 . Partition based spatial-merge join. In Proceedings of SIGMOD. 259--270. Jignesh M. Patel and David J. DeWitt. 1996. Partition based spatial-merge join. In Proceedings of SIGMOD. 259--270."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of EDBT. 632--643","author":"Pelekis Nikos","year":"2017","unstructured":"Nikos Pelekis , Panagiotis Tampakis , Marios Vodas , Costas Panagiotakis , and Yannis Theodoridis . 2017 . In-DBMS sampling-based sub-trajectory clustering . In Proceedings of EDBT. 632--643 . Nikos Pelekis, Panagiotis Tampakis, Marios Vodas, Costas Panagiotakis, and Yannis Theodoridis. 2017. In-DBMS sampling-based sub-trajectory clustering. In Proceedings of EDBT. 632--643."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of DBIS. 37--56","author":"Seidl Thomas","year":"2013","unstructured":"Thomas Seidl , Sergej Fries , and Brigitte Boden . 2013 . MR-DSJ: Distance-based self-join for large-scale vector data analysis with MapReduce . In Proceedings of DBIS. 37--56 . Thomas Seidl, Sergej Fries, and Brigitte Boden. 2013. MR-DSJ: Distance-based self-join for large-scale vector data analysis with MapReduce. In Proceedings of DBIS. 37--56."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137630"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0502-0"},{"key":"e_1_2_1_26_1","volume-title":"DITA: Distributed in-memory trajectory analytics. In SIGMOD. 725--740.","author":"Shang Zeyuan","year":"2018","unstructured":"Zeyuan Shang , Guoliang Li , and Zhifeng Bao . 2018 . DITA: Distributed in-memory trajectory analytics. In SIGMOD. 725--740. Zeyuan Shang, Guoliang Li, and Zhifeng Bao. 2018. DITA: Distributed in-memory trajectory analytics. In SIGMOD. 725--740."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831365"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_29_1","volume-title":"Reed","author":"Silva Yasin N.","year":"2012","unstructured":"Yasin N. Silva and Jason M . Reed . 2012 . Exploiting MapReduce-based similarity joins. In Proceedings of SIGMOD. 693--696. Yasin N. Silva and Jason M. Reed. 2012. Exploiting MapReduce-based similarity joins. In Proceedings of SIGMOD. 693--696."},{"key":"e_1_2_1_30_1","volume-title":"Tsosie","author":"Silva Yasin N.","year":"2012","unstructured":"Yasin N. Silva , Jason M. Reed , and Lisa M . Tsosie . 2012 . MapReduce-based similarity join for metric spaces. In Proceedings of Cloud-I. 3. Yasin N. Silva, Jason M. Reed, and Lisa M. Tsosie. 2012. MapReduce-based similarity join for metric spaces. In Proceedings of Cloud-I. 3."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2651821"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137655"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud\u201910","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark: Cluster computing with working sets . In Proceedings of 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud\u201910 , Boston, MA , June 22, 2010. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster computing with working sets. In Proceedings of 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud\u201910, Boston, MA, June 22, 2010."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183621"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2009.5289178"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:34Z","timestamp":1750197754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,4]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3373642"],"URL":"https:\/\/doi.org\/10.1145\/3373642","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2020,2,4]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}