{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:07:17Z","timestamp":1775912837233,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,9,12]],"date-time":"2018-09-12T00:00:00Z","timestamp":1536710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["III-1117766"],"award-info":[{"award-number":["III-1117766"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>The plethora of location-aware devices has led to countless location-based services in which huge amounts of spatiotemporal data get created every day. Several applications require efficient processing of queries on the locations of moving objects over time, i.e., the moving object trajectories. This calls for efficient trajectory-based indexing methods that capture both the spatial and temporal dimensions of the data in a way that minimizes the number of disk I\/Os required for both updating and querying. Most existing spatiotemporal index structures capture either the current locations of the moving objects or the entire history of the moving objects. Historical spatiotemporal indexing methods require multiple disk I\/Os to process new updates and use a discrete trajectory representation that may result in incomplete query results. In this article, we introduce the trails-tree, a disk-based data structure for indexing recent trajectories. The trails-tree requires half the number of disk I\/Os needed by other historical spatiotemporal indexing methods for the insertion and querying operations. We give a detailed description of the trails-tree, and we mathematically analyze its performance. Moreover, we present a novel query processing algorithm that ensures the completeness of the query result set. We experimentally verify the performance of the trails-tree using various real and synthetic datasets.<\/jats:p>","DOI":"10.1145\/3234941","type":"journal-article","created":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T12:07:33Z","timestamp":1536840453000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Disk-Based Indexing of Recent Trajectories"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8886-6364","authenticated-orcid":false,"given":"Ahmed R.","family":"Mahmood","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}]},{"given":"Ahmed M.","family":"Aly","sequence":"additional","affiliation":[{"name":"Google Inc., Amphitheatre Pkwy, Mountain View, USA"}]},{"given":"Tatiana","family":"Kuznetsova","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}]},{"given":"Saleh","family":"Basalamah","sequence":"additional","affiliation":[{"name":"Umm Al-Qura University, Mekkah, KSA"}]},{"given":"Walid G.","family":"Aref","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,9,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40235-7_3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98741"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559929"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525343"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-007-0030-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015231126594"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR\u201903)","author":"Chakka V. Prasad","unstructured":"V. Prasad Chakka , Adam Everspaugh , and Jignesh M. Patel . 2003. Indexing large trajectory data sets with SETI . In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR\u201903) . Asilomar, CA, USA. V. Prasad Chakka, Adam Everspaugh, and Jignesh M. Patel. 2003. Indexing large trajectory data sets with SETI. In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR\u201903). Asilomar, CA, USA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492101.1555371"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447829"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.17"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1922649.1922660"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_2_1_14_1","volume-title":"Moving Objects Databases","author":"G\u00fcting Ralf Hartmut","unstructured":"Ralf Hartmut G\u00fcting and Markus Schneider . 2005. Moving Objects Databases . Elsevier . Ralf Hartmut G\u00fcting and Markus Schneider. 2005. Moving Objects Databases. Elsevier."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994)","author":"Kamel Ibrahim","year":"1994","unstructured":"Ibrahim Kamel and Christos Faloutsos . 1994 . Hilbert R-tree: An improved R-tree using fractals . In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994) . Santiago de Chile, Chile, 500--509. Ibrahim Kamel and Christos Faloutsos. 1994. Hilbert R-tree: An improved R-tree using fractals. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994). Santiago de Chile, Chile, 500--509."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260804"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933358"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666427"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0046-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1263135.1263365"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645926.672019"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1039840"},{"key":"e_1_2_1_24_1","volume-title":"Spatial Databases: With Application to GIS. Morgan Kaufmann.","author":"Rigaux Philippe","year":"2001","unstructured":"Philippe Rigaux , Michel Scholl , and Agnes Voisard . 2001 . Spatial Databases: With Application to GIS. Morgan Kaufmann. Philippe Rigaux, Michel Scholl, and Agnes Voisard. 2001. Spatial Databases: With Application to GIS. Morgan Kaufmann."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases (VLDB\u201987)","author":"Sellis Timos","year":"1987","unstructured":"Timos Sellis , Nick Roussopoulos , and Christos Faloutsos . 1987 . The R+-tree: A dynamic index for multi-dimensional objects . In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB\u201987) . Brighton, England, 507--518. Timos Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R+-tree: A dynamic index for multi-dimensional objects. In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB\u201987). Brighton, England, 507--518."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0120-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.98"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.33"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases (VLDB\u201901)","author":"Tao Yufei","year":"2001","unstructured":"Yufei Tao and Dimitris Papadias . 2001 . MV3R-Tree: A spatio-temporal access method for timestamp and interval queries . In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB\u201901) . Roma, Italy, 431--440. Yufei Tao and Dimitris Papadias. 2001. MV3R-Tree: A spatio-temporal access method for timestamp and interval queries. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB\u201901). Roma, Italy, 431--440."},{"key":"e_1_2_1_30_1","volume-title":"Nascimento","author":"Theodoridis Yannis","year":"1999","unstructured":"Yannis Theodoridis , Jefferson R. O. Silva , and Mario A . Nascimento . 1999 . On the generation of spatiotemporal datasets. In Advances in Spatial Databases. Springer , 147--164. Yannis Theodoridis, Jefferson R. O. Silva, and Mario A. Nascimento. 1999. On the generation of spatiotemporal datasets. In Advances in Spatial Databases. Springer, 147--164."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s005300050094"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.125"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409635.1409677"},{"key":"e_1_2_1_36_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 Eng. 33 , 2 (2010), 32 -- 39 . Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Eng. 33, 2 (2010), 32--39.","journal-title":"IEEE Data Eng."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526816"},{"key":"e_1_2_1_38_1","volume-title":"Computing with Spatial Trajectories","author":"Zheng Yu","unstructured":"Yu Zheng and Xiaofang Zhou . 2011. Computing with Spatial Trajectories . Springer Science 8 Business Media. Yu Zheng and Xiaofang Zhou. 2011. Computing with Spatial Trajectories. Springer Science 8 Business Media."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3234941","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3234941","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3234941","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:20Z","timestamp":1750210760000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3234941"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,12]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3234941"],"URL":"https:\/\/doi.org\/10.1145\/3234941","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,12]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}