{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T10:43:38Z","timestamp":1773398618657,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,10,12]],"date-time":"2024-10-12T00:00:00Z","timestamp":1728691200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000266","name":"National Geospatial-Intelligence Agency","doi-asserted-by":"crossref","award":["HM0476-20-1-0009"],"award-info":[{"award-number":["HM0476-20-1-0009"]}],"id":[{"id":"10.13039\/100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Given trajectories with gaps (i.e., missing data), we investigate algorithms to identify abnormal gaps in trajectories which occur when a given moving object did not report its location, but other moving objects in the same geographic region periodically did. The problem is important due to its societal applications, such as improving maritime safety and regulatory enforcement for global security concerns, such as illegal fishing, illegal oil transfers, and trans-shipments. The problem is challenging due to the difficulty of bounding the possible locations of the moving object during a trajectory gap, and the very high computational cost of detecting gaps in such a large volume of location data. The current literature on anomalous trajectory detection assumes linear interpolation within gaps, which may not be able to detect abnormal gaps since objects within a given region may have traveled away from their shortest path. In preliminary work, we introduced an abnormal gap measure that uses a classical space-time prism model to bound an object's possible movement during the trajectory gap and provided a scalable memoized gap detection algorithm (Memo-AGD). In this article, we propose a space time-aware gap detection (STAGD) approach to leverage space-time indexing and merging of trajectory gaps. We also incorporate a dynamic region merge-based (DRM) approach to efficiently compute gap abnormality scores. We provide theoretical proofs that both algorithms are correct and complete and also provide analysis of asymptotic time complexity. Experimental results on synthetic and real-world maritime trajectory data show that the proposed approach substantially improves computation time over the baseline technique.<\/jats:p>","DOI":"10.1145\/3673235","type":"journal-article","created":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T13:29:17Z","timestamp":1718458157000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Physics-Based Abnormal Trajectory Gap Detection"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6908-6960","authenticated-orcid":false,"given":"Arun","family":"Sharma","sequence":"first","affiliation":[{"name":"University of Minnesota, Twin Cities, Minnesota, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5339-1832","authenticated-orcid":false,"given":"Subhankar","family":"Ghosh","sequence":"additional","affiliation":[{"name":"University of Minnesota, Twin Cities, Minnesota, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8217-3244","authenticated-orcid":false,"given":"Shashi","family":"Shekhar","sequence":"additional","affiliation":[{"name":"University of Minnesota, Twin Cities, Minnesota, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,10,12]]},"reference":[{"key":"e_1_3_2_2_1","unstructured":"2020. MarineTraffic. Retrieved from https:\/\/www.marinetraffic.com\/en\/ais\/"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071246.1071259"},{"key":"e_1_3_2_4_1","first-page":"109","volume-title":"Proceedings of the International Conference on GeoSensor Networks","author":"Bakalov Petko","year":"2006","unstructured":"Petko Bakalov and Vassilis J. Tsotras. 2006. Continuous spatiotemporal trajectory joins. In Proceedings of the International Conference on GeoSensor Networks. Springer, 109\u2013128."},{"key":"e_1_3_2_5_1","unstructured":"BOEM and NOAA. 2020. MarineCadastre. Retrieved from https:\/\/marinecadastre.gov\/ais\/"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541880.1541882"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2013.2238531"},{"key":"e_1_3_2_8_1","first-page":"453","article-title":"Jackknife variance estimation for nearest-neighbor imputation","volume":"96","author":"Chen Jiahua","year":"2001","unstructured":"Jiahua Chen and Jun Shao. 2001. Jackknife variance estimation for nearest-neighbor imputation. Journal of the American Statistical Association 96, 453 (2001), 260\u2013269.","journal-title":"Journal of the American Statistical Association"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653809"},{"key":"e_1_3_2_11_1","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1109\/ICDE.2008.4497506","volume-title":"Proceedings of the 2008 IEEE 24th International Conference on Data Engineering","author":"Cheng Reynold","year":"2008","unstructured":"Reynold Cheng, Jinchuan Chen, Mohamed Mokbel, and Chi-Yin Chow . 2008. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. IEEE, 973\u2013982."},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2008.25"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1057\/PALGRAVE.IVS.9500182"},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1137\/1.9781611978032.71","volume-title":"Proceedings of the 2024 SIAM International Conference on Data Mining (SDM)","author":"Farhadloo Majid","year":"2024","unstructured":"Majid Farhadloo, Arun Sharma, Jayant Gupta, Alexey Leontovich, Svetomir N. Markovic, and Shashi Shekhar. 2024. Towards spatially-lucid AI classification in non-euclidean space: An application for MxIF oncology data. In Proceedings of the 2024 SIAM International Conference on Data Mining (SDM). SIAM, 616\u2013624."},{"key":"e_1_3_2_15_1","volume-title":"Applied Regression Analysis and Generalized Linear Models","author":"Fox John","year":"2015","unstructured":"John Fox. 2015. Applied Regression Analysis and Generalized Linear Models. Sage Publications."},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3557989.3566158"},{"key":"e_1_3_2_17_1","volume-title":"Proceedings of the 12th International Conference on Geographic Information Science (GIScience \u201923)","author":"Ghosh Subhankar","year":"2023","unstructured":"Subhankar Ghosh, Jayant Gupta, Arun Sharma, Shuai An, and Shashi Shekhar. 2023. Reducing false discoveries in statistically-significant regional-colocation mining: A summary of results. In Proceedings of the 12th International Conference on Geographic Information Science (GIScience \u201923). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_18_1","unstructured":"S. Gibbens. 2018. How illegal fishing is being tracked from space. National Geographic."},{"key":"e_1_3_2_19_1","first-page":"1","volume-title":"Proceedings of the 30th International Conference on Advances in Geographic Information Systems","author":"Gupta Jayant","year":"2022","unstructured":"Jayant Gupta and Arun Sharma. 2022. Mining taxonomy-aware colocations: A summary of results. In Proceedings of the 30th International Conference on Advances in Geographic Information Systems, 1\u201311."},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-006-0016-x"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0262-6"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810802097485"},{"key":"e_1_3_2_23_1","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-81-322-2250-7_29","volume-title":"Information Systems Design and Intelligent Applications: Proceedings of 2nd International Conference INDIA 2015","volume":"1","author":"Kumar K. Vimal","year":"2015","unstructured":"K. Vimal Kumar, Divakar Yadav, and Arun Sharma. 2015. Graph based technique for Hindi text summarization. In Information Systems Design and Intelligent Applications: Proceedings of 2nd International Conference INDIA 2015, Vol. 1. Springer, 301\u2013310."},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-015-0845-4"},{"key":"e_1_3_2_25_1","unstructured":"Milton Lim. 2021. Gauss Least Squares and the Missing Planet. Retrieved from https:\/\/www.actuaries.digital\/2021\/03\/31\/gauss-least-squares-and-the-missing-planet\/"},{"key":"e_1_3_2_26_1","first-page":"490","volume-title":"Proceeding of the 21th International Conference on Very Large Data Bases","author":"Rake& Agrawal King-lp Lin and Harpreet S.Sawhney Kyuseok Shim","year":"1995","unstructured":"Rake& Agrawal King-lp Lin and Harpreet S.Sawhney Kyuseok Shim. 1995. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In Proceeding of the 21th International Conference on Very Large Data Bases. Citeseer, 490\u2013501."},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.02.011"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799108927856"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.3390\/e15062218"},{"key":"e_1_3_2_30_1","first-page":"111","volume-title":"Proceedings of the International Symposium on Spatial Databases","author":"Pfoser D.","year":"1999","unstructured":"D. Pfoser and C. S. Jensen. 1999. Capturing the uncertainty of moving-object representations. In Proceedings of the International Symposium on Spatial Databases. Springer, 111\u2013131."},{"key":"e_1_3_2_31_1","first-page":"395","article-title":"Novel approaches to the indexing of moving object trajectories","author":"Pfoser Dieter","year":"2000","unstructured":"Dieter Pfoser, Christian S. Jensen, and Yannis Theodoridis. 2000. Novel approaches to the indexing of moving object trajectories. In Proceedings of the Very Large Data Base (VLDB), 395\u2013406.","journal-title":"Proceedings of the Very Large Data Base (VLDB)"},{"key":"e_1_3_2_32_1","first-page":"131","volume-title":"Proceedings of the Section on Survey Research Methods, American Statistical Association","author":"Rancourt E.","year":"1999","unstructured":"E. Rancourt. 1999. Estimation with nearest neighbour imputation at statistics Canada. In Proceedings of the Section on Survey Research Methods, American Statistical Association, 131\u2013138."},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1266"},{"key":"e_1_3_2_34_1","first-page":"1178","volume-title":"Proceedings of the VLDB Endowment","author":"Shang Shuo","year":"2017","unstructured":"Shuo Shang, Lisi Chen, Zhewei Wei, Christian S. Jensen, Kai Zheng, and Panos Kalnis. 2017. Trajectory similarity join in spatial networks. In Proceedings of the VLDB Endowment, 1178\u20131189."},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.5194\/agile-giss-3-14-2022"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3557915.3561033"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.COSIT.2022.26"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","unstructured":"Arun Sharma Zhe Jiang and Shashi Shekhar. 2022. Spatiotemporal data mining: A survey. arXiv:2206.12753 . Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2206.12753","DOI":"10.48550\/arXiv.2206.12753"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3467977"},{"key":"e_1_3_2_40_1","first-page":"1","volume-title":"Proceedings of the 11th International Conference on Geographic Information Science (GIScience \u201921)-Part I","author":"Sharma Arun","year":"2020","unstructured":"Arun Sharma, Xun Tang, Jayant Gupta, Majid Farhadloo, and Shashi Shekhar. 2020. Analyzing trajectory gaps for possible rendezvous: A summary of results. In Proceedings of the 11th International Conference on Geographic Information Science (GIScience \u201921)-Part I. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 1\u201316."},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2651821"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2010.76"},{"key":"e_1_3_2_43_1","unstructured":"Wikipedia. 2021. Space Shuttle Columbia Disaster. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Space_Shuttle_Columbia_disaster"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658811003619150"},{"key":"e_1_3_2_45_1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1109\/ICDE.1998.655778","volume-title":"Proceedings 14th International Conference on Data Engineering","author":"Yi Byoung-Kee","year":"1998","unstructured":"Byoung-Kee Yi, Hosagrahar V. Jagadish, and Christos Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings 14th International Conference on Data Engineering. IEEE, 201\u2013208."},{"key":"e_1_3_2_46_1","first-page":"11","article-title":"Applying frequent-pattern mining and time geography to impute gaps in smartphone-based human-movement data","volume":"35","author":"Zhao Pengxiang","year":"2021","unstructured":"Pengxiang Zhao, David Jonietz, and Martin Raubal. 2021. Applying frequent-pattern mining and time geography to impute gaps in smartphone-based human-movement data. International Journal of Geographical Information Science 35, 11 (2021), 2187\u20132215.","journal-title":"International Journal of Geographical Information Science"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743025"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673235","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3673235","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3673235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:25Z","timestamp":1750294705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,12]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3673235"],"URL":"https:\/\/doi.org\/10.1145\/3673235","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,12]]},"assertion":[{"value":"2023-09-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}