{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:33:01Z","timestamp":1773246781560,"version":"3.50.1"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T00:00:00Z","timestamp":1623628800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Australian Research Council Discovery Projects ARC","award":["DP180102870 ARC"],"award-info":[{"award-number":["DP180102870 ARC"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            We present a scalable approach for range and\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor queries under computationally expensive metrics, like the continuous Fr\u00e9chet distance on trajectory data. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories, regardless of the trajectory\u2019s individual sizes or the spatial dimension, which allows one to exploit low \u201cintrinsic dimensionality\u201d of datasets for effective search space pruning.\n          <\/jats:p>\n          <jats:p>Since the distance computation is expensive, generic metric indexing methods are rendered impractical. We present strategies that (i) improve on known upper and lower bound computations, (ii) build cluster trees without any or very few distance calls, and (iii) search using bounds for metric pruning, interval orderings for reduction, and randomized pivoting for reporting the final results.<\/jats:p>\n          <jats:p>\n            We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world datasets. The results show improvement over state-of-the-art methods for exact queries, and even further speedups are achieved for queries that may return approximate results. Surprisingly, the majority of exact nearest-neighbor queries on real datasets are answered\n            <jats:italic>without any<\/jats:italic>\n            distance computations.\n          <\/jats:p>","DOI":"10.1145\/3460121","type":"journal-article","created":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T12:33:24Z","timestamp":1623674004000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Practical Index Structure Supporting Fr\u00e9chet Proximity Queries among Trajectories"],"prefix":"10.1145","volume":"7","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Sydney, Australia"}]},{"given":"Michael","family":"Horton","sequence":"additional","affiliation":[{"name":"SPORTLOGiQ Inc., Canada"}]},{"given":"John","family":"Pfeifer","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6901-3035","authenticated-orcid":false,"given":"Martin P.","family":"Seybold","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2021,6,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"ACM. 2017.ACM SIGSPATIAL Cup 2017\u2014Range queries in very large databases of trajectories.Retrieved from: http:\/\/sigspatial2017.sigspatial.org\/giscup2017\/.  ACM. 2017.ACM SIGSPATIAL Cup 2017\u2014Range queries in very large databases of trajectories.Retrieved from: http:\/\/sigspatial2017.sigspatial.org\/giscup2017\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175328"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920526"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1165-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-1396-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_16"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274895.3274943"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586090"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140062"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1290250"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 35th International Symposium on Computational Geometry.17:1\u201317:21","author":"Bringmann Karl","year":"2019","unstructured":"Karl Bringmann , Marvin K\u00fcnnemann , and Andr\u00e9 Nusser . 2019 . Walking the dog fast in practice: Algorithm\u00a0engineering of the fr\u00e9chet distance . In Proceedings of the 35th International Symposium on Computational Geometry.17:1\u201317:21 . DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.17. 10.4230\/LIPIcs.SoCG.2019.17 Karl Bringmann, Marvin K\u00fcnnemann, and Andr\u00e9 Nusser. 2019. Walking the dog fast in practice: Algorithm\u00a0engineering of the fr\u00e9chet distance. In Proceedings of the 35th International Symposium on Computational Geometry.17:1\u201317:21. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.17."},{"key":"e_1_2_1_18_1","first-page":"46","article-title":"Approximability of the discrete Fr\u00e9chet distance","volume":"7","author":"Bringmann Karl","year":"2015","unstructured":"Karl Bringmann and Wolfgang Mulzer . 2015 . Approximability of the discrete Fr\u00e9chet distance . J. Comput. Geom. 7 , 2 (2015), 46 \u2013 76 . Karl Bringmann and Wolfgang Mulzer. 2015. Approximability of the discrete Fr\u00e9chet distance. J. Comput. Geom. 7, 2 (2015), 46\u201376.","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9878-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140064"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645923.671005"},{"key":"e_1_2_1_23_1","volume-title":"\u201csb(S)","author":"Clarkson Kenneth L.","year":"2003","unstructured":"Kenneth L. Clarkson . 2003. Nearest Neighbor Searching in Metric Spaces: Experimental Results for \u201csb(S) .\u201d ( 2003 ). Retrieved from: https:\/\/kenclarkson.org\/Msb\/white_paper.pdf. Kenneth L. Clarkson. 2003. Nearest Neighbor Searching in Metric Spaces: Experimental Results for \u201csb(S).\u201d (2003). Retrieved from: https:\/\/kenclarkson.org\/Msb\/white_paper.pdf."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715923"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2664.2008.01589.x"},{"key":"e_1_2_1_26_1","unstructured":"Sanjoy Dasgupta. 2013. Lecture Notes on k-center clustering. Retrieved from https:\/\/cseweb.ucsd.edu\/ dasgupta\/291-geom\/kcenter.pdf.  Sanjoy Dasgupta. 2013. Lecture Notes on k-center clustering. Retrieved from https:\/\/cseweb.ucsd.edu\/ dasgupta\/291-geom\/kcenter.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.11.006"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140023"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry. 37:1\u201337:16","author":"Driemel Anne","year":"2017","unstructured":"Anne Driemel and Francesco Silvestri . 2017 . Locality-sensitive hashing of curves . In Proceedings of the 33rd International Symposium on Computational Geometry. 37:1\u201337:16 . DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.37. 10.4230\/LIPIcs.SoCG.2017.37 Anne Driemel and Francesco Silvestri. 2017. Locality-sensitive hashing of curves. In Proceedings of the 33rd International Symposium on Computational Geometry. 37:1\u201337:16. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.37."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140063"},{"key":"e_1_2_1_33_1","unstructured":"David Eppstein. 2007. Blum-style analysis of Quickselect. Retrieved from https:\/\/11011110.github.io\/blog\/2007\/10\/09\/blum-style-analysis-of.html.  David Eppstein. 2007. Blum-style analysis of Quickselect. Retrieved from https:\/\/11011110.github.io\/blog\/2007\/10\/09\/blum-style-analysis-of.html."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_19"},{"key":"e_1_2_1_35_1","volume-title":"Frey and Delbert Dueck","author":"Brendan","year":"2007","unstructured":"Brendan J. Frey and Delbert Dueck . 2007 . Clustering by passing messages between data points. Science 315, 5814 (2007), 972\u2013976. Brendan J. Frey and Delbert Dueck. 2007. Clustering by passing messages between data points. Science 315, 5814 (2007), 972\u2013976."},{"key":"e_1_2_1_36_1","first-page":"2475","article-title":"Pigeon navigation: exposure to environmental odours prior release is sufficient for homeward orientation, but not for homing","volume":"2019","author":"Gagliardo Anna","year":"2016","unstructured":"Anna Gagliardo , Enrica Pollonara , and Martin Wikelski . 2016 . Pigeon navigation: exposure to environmental odours prior release is sufficient for homeward orientation, but not for homing . J. Experim. Biol. 2019 , 16 (2016), 2475 \u2013 2480 . Anna Gagliardo, Enrica Pollonara, and Martin Wikelski. 2016. Pigeon navigation: exposure to environmental odours prior release is sufficient for homeward orientation, but not for homing. J. Experim. Biol. 2019, 16 (2016), 2475\u20132480.","journal-title":"J. Experim. Biol."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1004089"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.02.003"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946308"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1804437"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513414"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.23"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.235263"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_49_1","unstructured":"Roland Kays James Flowers and Suzanne Kennedy-Stoskopf. 2016. Cat Tracker Project. Retrieved from http:\/\/www.movebank.org\/.  Roland Kays James Flowers and Suzanne Kennedy-Stoskopf. 2016. Cat Tracker Project. Retrieved from http:\/\/www.movebank.org\/."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2993953.2994027"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. 140\u2013151","author":"Ashraf","unstructured":"Ashraf M. Kibriya and Eibe Frank. 2007. An empirical comparison of exact nearest neighbour algorithms . In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. 140\u2013151 . Ashraf M. Kibriya and Eibe Frank. 2007. An empirical comparison of exact nearest neighbour algorithms. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. 140\u2013151."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1209\/epl\/i2004-10483-y"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982913"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.3390\/s17081792"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735466"},{"key":"e_1_2_1_56_1","unstructured":"Microsoft. 2012. Microsoft Research Asia GeoLife GPS Trajectories. Retrieved from http:\/\/www.microsoft.com\/en-us\/download\/details. aspx?id=52367.  Microsoft. 2012. Microsoft Research Asia GeoLife GPS Trajectories. Retrieved from http:\/\/www.microsoft.com\/en-us\/download\/details. aspx?id=52367."},{"key":"e_1_2_1_57_1","first-page":"197","article-title":"Towards a discipline of experimental algorithmics. Data Struct., Near Neighb. Searc., Methodol","volume":"59","author":"Moret Bernard M. E.","year":"2002","unstructured":"Bernard M. E. Moret . 2002 . Towards a discipline of experimental algorithmics. Data Struct., Near Neighb. Searc., Methodol .: Fifth Sixth DIMACS Implem. Chall. 59 (2002), 197 \u2013 213 . Bernard M. E. Moret. 2002. Towards a discipline of experimental algorithmics. Data Struct., Near Neighb. Searc., Methodol.: Fifth Sixth DIMACS Implem. Chall. 59 (2002), 197\u2013213.","journal-title":"Fifth Sixth DIMACS Implem. Chall."},{"key":"e_1_2_1_58_1","unstructured":"NOAA. 2017. National Hurricane Center National Oceanic and Atmospheric Administration HURDAT2 Atlantic hurricane database. Retrieved from http:\/\/www.nhc.noaa.gov\/data\/.  NOAA. 2017. National Hurricane Center National Oceanic and Atmospheric Administration HURDAT2 Atlantic hurricane database. Retrieved from http:\/\/www.nhc.noaa.gov\/data\/."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0178318"},{"key":"e_1_2_1_60_1","volume-title":"Applying deep learning to basketball trajectories. arXiv preprint arXiv:1608.03793","author":"Shah Rajiv","year":"2016","unstructured":"Rajiv Shah and Rob Romijnders . 2016. Applying deep learning to basketball trajectories. arXiv preprint arXiv:1608.03793 ( 2016 ). Rajiv Shah and Rob Romijnders. 2016. Applying deep learning to basketball trajectories. arXiv preprint arXiv:1608.03793 (2016)."},{"key":"e_1_2_1_61_1","unstructured":"STATS. 2015. STATS LLC - Data Science. Retrieved from http:\/\/www.stats.com\/data-science\/.  STATS. 2015. STATS LLC - Data Science. Retrieved from http:\/\/www.stats.com\/data-science\/."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(91)90146-M"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_2_1_64_1","first-page":"64","article-title":"Markov processes over denumerable products of spaces, describing large systems of automata","volume":"5","author":"Vaserstein Leonid Nisonovich","year":"1969","unstructured":"Leonid Nisonovich Vaserstein . 1969 . Markov processes over denumerable products of spaces, describing large systems of automata . Problemy Peredachi Informatsii 5 , 3 (1969), 64 \u2013 72 . Leonid Nisonovich Vaserstein. 1969. Markov processes over denumerable products of spaces, describing large systems of automata. Problemy Peredachi Informatsii 5, 3 (1969), 64\u201372.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.878994"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671192"},{"key":"e_1_2_1_67_1","first-page":"17061","article-title":"True navigation in migrating gulls requires intact olfactory nerves. Sci","volume":"5","author":"Wikelski Martin","year":"2015","unstructured":"Martin Wikelski , Elena Arriero , Anna Gagliardo , Richard A. Holland , Markku J. Huttunen , Risto Juvaste , Inge Mueller , Grigori Tertitski , Kasper Thorup , Martin Wild , et\u00a0al. 2015 . True navigation in migrating gulls requires intact olfactory nerves. Sci . Rep. 5 (2015), 17061 . Martin Wikelski, Elena Arriero, Anna Gagliardo, Richard A. Holland, Markku J. Huttunen, Risto Juvaste, Inge Mueller, Grigori Tertitski, Kasper Thorup, Martin Wild, et\u00a0al. 2015. True navigation in migrating gulls requires intact olfactory nerves. Sci. Rep. 5 (2015), 17061.","journal-title":"Rep."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/11840930_66"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137655"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313789"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213885"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:18Z","timestamp":1750188618000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,14]]},"references-count":72,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3460121"],"URL":"https:\/\/doi.org\/10.1145\/3460121","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,14]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}