{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T05:15:17Z","timestamp":1780722917731,"version":"3.54.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T00:00:00Z","timestamp":1741132800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Similarity search is the problem of finding in a collection of objects those that are similar to a given query object. It is a fundamental problem in modern applications and the objects considered may be as diverse as locations in space, text documents, images, X (formerly known as Twitter) messages, or trajectories of moving objects.<\/jats:p>\n          <jats:p>\n            In this article, we are motivated by the latter application. Trajectories are recorded movements of mobile objects such as vehicles, animals, public transportation, or parts of the human body. We propose a novel distance function called\n            <jats:italic>DistanceAvg<\/jats:italic>\n            to capture the similarity of such movements. To be practical, it is necessary to provide indexing for this distance measure.\n          <\/jats:p>\n          <jats:p>\n            Fortunately we do not need to start from scratch. A generic and unifying approach is metric space, which organizes the set of objects solely by a distance (similarity) function with certain natural properties. Our function\n            <jats:italic>DistanceAvg<\/jats:italic>\n            is a metric.\n          <\/jats:p>\n          <jats:p>\n            Although metric indexes have been studied for decades and many such structures are available, they do not offer the best performance with trajectories. In this article, we propose a new design, which outperforms the best existing indexes for\n            <jats:italic>kNN<\/jats:italic>\n            queries and is equally good for range queries. It is especially suitable for expensive distance functions as they occur in trajectory similarity search. In many applications,\n            <jats:italic>kNN<\/jats:italic>\n            queries are more practical than range queries as it may be difficult to determine an appropriate search radius. Our index provides exact result sets for the given distance function.\n          <\/jats:p>","DOI":"10.1145\/3716825","type":"journal-article","created":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T09:09:57Z","timestamp":1739005797000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index for kNN and Range Queries"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6260-4051","authenticated-orcid":false,"given":"Ralf Hartmut","family":"G\u00fcting","sequence":"first","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik und Informatik, University of Hagen, Hagen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7690-5073","authenticated-orcid":false,"given":"Suvam Kumar","family":"Das","sequence":"additional","affiliation":[{"name":"University of New Brunswick, Fredericton, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4131-819X","authenticated-orcid":false,"given":"Fabio","family":"Vald\u00e9s","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik und Informatik, University of Hagen, Hagen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0681-9685","authenticated-orcid":false,"given":"Suprio","family":"Ray","sequence":"additional","affiliation":[{"name":"University of New Brunswick, Fredericton, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1142\/S0218195995000064","article-title":"Computing the Fr\u00e9chet distance between two polygonal curves","volume":"5","author":"Alt Helmut","year":"1995","unstructured":"Helmut Alt and Michael Godau. 1995. Computing the Fr\u00e9chet distance between two polygonal curves. Int. J. Comput. Geometry Appl. 5, 1-2 (1995), 75\u201391.","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"3","key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/328939.328959","article-title":"Indexing large metric spaces for similarity search queries","volume":"24","author":"Bozkaya Tolga","year":"1999","unstructured":"Tolga Bozkaya and Meral Ozsoyoglu. 1999. Indexing large metric spaces for similarity search queries. ACM Trans. Database Syst. 24, 3 (September1999), 361\u2013404.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_4_4_2","first-page":"574","volume-title":"Proceedings of the 21st International Conference on Very Large Data Bases (VLDB\u201995)","author":"Brin Sergey","year":"1995","unstructured":"Sergey Brin. 1995. Near neighbor search in large metric spaces. In Proceedings of the 21st International Conference on Very Large Data Bases (VLDB\u201995). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 574\u2013584."},{"key":"e_1_3_4_5_2","first-page":"75","volume-title":"Proceedings of the 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000","author":"Ch\u00e1vez Edgar","year":"2000","unstructured":"Edgar Ch\u00e1vez and Gonzalo Navarro. 2000. An effective clustering algorithm to index high dimensional metric spaces. In Proceedings of the 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000. IEEE Computer Society, Washington, DC, USA, 75\u201386."},{"issue":"3","key":"e_1_3_4_6_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/502807.502808","article-title":"Searching in metric spaces","volume":"33","author":"Ch\u00e1vez Edgar","year":"2001","unstructured":"Edgar Ch\u00e1vez, Gonzalo Navarro, Ricardo Baeza-Yates, and Jos\u00e9 Luis Marroqu\u00edn. 2001. Searching in metric spaces. ACM Comput. Surv. 33, 3 (September2001), 273\u2013321.","journal-title":"ACM Comput. Surv."},{"issue":"6","key":"e_1_3_4_7_2","first-page":"128:1\u2013128:39","article-title":"Indexing metric spaces for exact similarity search","volume":"55","author":"Chen Lu","year":"2023","unstructured":"Lu Chen, Yunjun Gao, Xuan Song, Zheng Li, Yifan Zhu, Xiaoye Miao, and Christian S. Jensen. 2023. Indexing metric spaces for exact similarity search. ACM Comput. Surv. 55, 6 (2023), 128:1\u2013128:39.","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_4_8_2","first-page":"792","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases, VLDB","author":"Chen Lei","year":"2004","unstructured":"Lei Chen and Raymond T. Ng. 2004. On the marriage of Lp-norms and edit distance. In Proceedings of the 30th International Conference on Very Large Data Bases, VLDB. Morgan Kaufmann, 792\u2013803."},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1145\/1066157.1066213","volume-title":"Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data","author":"Chen Lei","year":"2005","unstructured":"Lei Chen, M. Tamer \u00d6zsu, and Vincent Oria. 2005. Robust and fast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. 491\u2013502."},{"key":"e_1_3_4_10_2","first-page":"426","volume-title":"VLDB\u201997, Proceedings of the 23rd International Conference on Very Large Data Bases","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An efficient access method for similarity search in metric spaces. In VLDB\u201997, Proceedings of the 23rd International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, CA, USA, 426\u2013435."},{"key":"e_1_3_4_11_2","first-page":"185","volume-title":"Voronoi Trees and Clustering Problems","author":"Dehne Frank","year":"1988","unstructured":"Frank Dehne and Hartmut Noltemeier. 1988. Voronoi Trees and Clustering Problems. Springer-Verlag, Berlin, 185\u2013194."},{"key":"e_1_3_4_12_2","first-page":"133","volume-title":"Proceedings of the 2004 International Conference on Current Trends in Database Technology - EDBT 2004 Workshops, EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb","volume":"3268","author":"Dohnal Vlastislav","year":"2004","unstructured":"Vlastislav Dohnal. 2004. An access structure for similarity search in metric spaces. In Proceedings of the 2004 International Conference on Current Trends in Database Technology - EDBT 2004 Workshops, EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb(. Lecture Notes in Computer Science, Vol. 3268, Springer, Berlin, 133\u2013143."},{"issue":"2","key":"e_1_3_4_13_2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","article-title":"Algorithms for the reduction of the number of points required to represent a digitized line or its caricature","volume":"10","author":"Douglas David H.","year":"1973","unstructured":"David H. Douglas and Thomas K. Peucker. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica 10, 2 (1973), 112\u2013122.","journal-title":"Cartographica"},{"key":"e_1_3_4_14_2","first-page":"6","article-title":"Speeding up spatial approximation search in metric spaces","volume":"14","author":"Figueroa Karina","year":"2010","unstructured":"Karina Figueroa, Edgar Chavez, Gonzalo Navarro, and Rodrigo Paredes. 2010. Speeding up spatial approximation search in metric spaces. ACM J. Exp. Algorithmics 14, Article 6 (January2010), 21 pages.","journal-title":"ACM J. Exp. Algorithmics"},{"key":"e_1_3_4_15_2","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/342009.335426","volume-title":"Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data","author":"Forlizzi Luca","year":"2000","unstructured":"Luca Forlizzi, Ralf Hartmut G\u00fcting, Enrico Nardelli, and Markus Schneider. 2000. A data model and data structures for moving objects databases. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Weidong Chen, Jeffrey F. Naughton, and Philip A. Bernstein (Eds.), ACM, 319\u2013330."},{"key":"e_1_3_4_16_2","first-page":"816","volume-title":"Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering","author":"Frentzos Elias","year":"2007","unstructured":"Elias Frentzos, Kostas Gratsias, and Yannis Theodoridis. 2007. Index-based most similar trajectory search. In Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering. 816\u2013825."},{"key":"e_1_3_4_17_2","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/PL00010672","article-title":"Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances","volume":"9","author":"Fu Ada Wai-Chee","year":"2000","unstructured":"Ada Wai-Chee Fu, Polly Mei-Shuen Chan, Yin-Ling Cheung, and Yiu Sang Moon. 2000. Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances. VLDB J. 9, 2 (2000), 154\u2013173.","journal-title":"VLDB J."},{"issue":"2","key":"e_1_3_4_18_2","first-page":"56","article-title":"SECONDO: A platform for moving objects database research and for publishing and integrating research implementations","volume":"33","author":"G\u00fcting Ralf Hartmut","year":"2010","unstructured":"Ralf Hartmut G\u00fcting, Thomas Behr, and Christian D\u00fcntgen. 2010. SECONDO: A platform for moving objects database research and for publishing and integrating research implementations. IEEE Data Eng. Bull. 33, 2 (2010), 56\u201363.","journal-title":"IEEE Data Eng. Bull."},{"issue":"4","key":"e_1_3_4_19_2","first-page":"1009","article-title":"Distributed arrays: An algebra for generic distributed query processing","volume":"39","author":"G\u00fcting Ralf Hartmut","year":"2021","unstructured":"Ralf Hartmut G\u00fcting, Thomas Behr, and January Kristof Nidzwetzki. 2021. Distributed arrays: An algebra for generic distributed query processing. Distrib. Parallel Databases 39, 4 (2021), 1009\u20131064.","journal-title":"Distrib. Parallel Databases"},{"issue":"1","key":"e_1_3_4_20_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/352958.352963","article-title":"A foundation for representing and querying moving objects","volume":"25","author":"G\u00fcting Ralf Hartmut","year":"2000","unstructured":"Ralf Hartmut G\u00fcting, Michael H. B\u00f6hlen, Martin Erwig, Christian S. Jensen, Nikos A. Lorentzos, Markus Schneider, and Michalis Vazirgiannis. 2000. A foundation for representing and querying moving objects. ACM Trans. Database Syst. 25, 1 (2000), 1\u201342.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_4_21_2","article-title":"Voronoi-Partitioned Metric Space: The N-tree","author":"G\u00fcting Ralf Hartmut","year":"2023","unstructured":"Ralf Hartmut G\u00fcting, Suvam Kumar Das, Fabio Vald\u00e9s, and Suprio Ray. 2023. Voronoi-Partitioned Metric Space: The N-tree. FernUniversit\u00e4t in Hagen, Informatik-Report 384.","journal-title":"FernUniversit\u00e4t in Hagen, Informatik-Report 384"},{"key":"e_1_3_4_22_2","first-page":"1115","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE\u201905)","author":"G\u00fcting Ralf Hartmut","year":"2005","unstructured":"Ralf Hartmut G\u00fcting, Victor Teixeira de Almeida, Dirk Ansorge, Thomas Behr, Zhiming Ding, Thomas H\u00f6se, Frank Hoffmann, Markus Spiekermann, and Ulrich Telle. 2005. SECONDO: An extensible DBMS platform for research prototyping and teaching. In Proceedings of the International Conference on Data Engineering (ICDE\u201905). IEEE Computer Society, 1115\u20131116."},{"key":"e_1_3_4_23_2","volume-title":"Moving Objects Databases","author":"G\u00fcting Ralf Hartmut","year":"2005","unstructured":"Ralf Hartmut G\u00fcting and Markus Schneider. 2005. Moving Objects Databases. Morgan Kaufmann."},{"issue":"5","key":"e_1_3_4_24_2","doi-asserted-by":"crossref","first-page":"2191","DOI":"10.1109\/TKDE.2023.3323535","article-title":"Spatio-temporal trajectory similarity measures: A comprehensive survey and quantitative study","volume":"36","author":"Hu Danlei","year":"2024","unstructured":"Danlei Hu, Lu Chen, Hanxi Fang, Ziquan Fang, Tianyi Li, and Yunjun Gao. 2024. Spatio-temporal trajectory similarity measures: A comprehensive survey and quantitative study. IEEE Trans. Knowl. Data Eng. 36, 5 (2024), 2191\u20132212.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_4_25_2","first-page":"356","volume-title":"Proceedings of the 1st International Conference on Web-Age Information Management, WAIM 2000","volume":"1846","author":"Ishikawa Masahiro","year":"2000","unstructured":"Masahiro Ishikawa, Hanxiong Chen, Kazutaka Furuse, Jeffrey Xu Yu, and Nobuo Ohbo. 2000. MB+Tree: A dynamically updatable metric index for similarity searches. In Proceedings of the 1st International Conference on Web-Age Information Management, WAIM 2000. Lecture Notes in Computer Science, Vol. 1846, Springer, Berlin, 356\u2013373."},{"key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1109\/TSE.1983.235263","article-title":"A data structure and an algorithm for the nearest point problem","volume":"9","author":"Kalantari Iraj","year":"1983","unstructured":"Iraj Kalantari and Gerard McDonald. 1983. A data structure and an algorithm for the nearest point problem. IEEE Trans. Softw. Eng. 9, 5 (1983), 631\u2013634.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/347090.347153","volume-title":"Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Keogh Eamonn J.","year":"2000","unstructured":"Eamonn J. Keogh and Michael J. Pazzani. 2000. Scaling up dynamic time warping for datamining applications. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 285\u2013289."},{"issue":"6","key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1093\/comjnl\/46.6.680","article-title":"Algorithms for moving objects databases","volume":"46","author":"Lema Jos\u00e9 Antonio Cotelo","year":"2003","unstructured":"Jos\u00e9 Antonio Cotelo Lema, Luca Forlizzi, Ralf Hartmut G\u00fcting, Enrico Nardelli, and Markus Schneider. 2003. Algorithms for moving objects databases. Comput. J. 46, 6 (2003), 680\u2013712.","journal-title":"Comput. J."},{"issue":"1","key":"e_1_3_4_29_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0167-8655(94)90095-7","article-title":"A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements","volume":"15","author":"Mic\u00f3 Mar\u00eda Luisa","year":"1994","unstructured":"Mar\u00eda Luisa Mic\u00f3, Jos\u00e9 Oncina, and Enrique Vidal. 1994. A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recogn. Lett. 15, 1 (1994), 9\u201317.","journal-title":"Pattern Recogn. Lett."},{"key":"e_1_3_4_30_2","first-page":"17","volume-title":"Proceedings of the 4th International Conference on Similarity Search and Applications, SISAP 2011","author":"Mosko Juraj","year":"2011","unstructured":"Juraj Mosko, Jakub Lokoc, and Tom\u00e1s Skopal. 2011. Clustered pivot tables for I\/O-optimized similarity search. In Proceedings of the 4th International Conference on Similarity Search and Applications, SISAP 2011. ACM, New York, NY, USA, 17\u201324."},{"issue":"3","key":"e_1_3_4_31_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s10844-006-9953-7","article-title":"Time-focused clustering of trajectories of moving objects","volume":"27","author":"Nanni Mirco","year":"2006","unstructured":"Mirco Nanni and Dino Pedreschi. 2006. Time-focused clustering of trajectories of moving objects. J. Intell. Inf. Syst. 27, 3 (2006), 267\u2013289.","journal-title":"J. Intell. Inf. Syst."},{"key":"e_1_3_4_32_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.is.2016.03.009","article-title":"New dynamic metric indices for secondary memory","volume":"59","author":"Navarro Gonzalo","year":"2016","unstructured":"Gonzalo Navarro and Nora Reyes. 2016. New dynamic metric indices for secondary memory. Inf. Syst. 59, C (July2016), 48\u201378.","journal-title":"Inf. Syst."},{"issue":"4","key":"e_1_3_4_33_2","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1016\/j.is.2011.01.002","article-title":"Fully dynamic metric access methods based on hyperplane partitioning","volume":"36","author":"Navarro Gonzalo","year":"2011","unstructured":"Gonzalo Navarro and Roberto Uribe-Paredes. 2011. Fully dynamic metric access methods based on hyperplane partitioning. Inf. Syst. 36, 4 (June2011), 734\u2013747.","journal-title":"Inf. Syst."},{"key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/3-540-55488-2_27","volume-title":"Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative.","author":"Noltemeier Hartmut","year":"1992","unstructured":"Hartmut Noltemeier, Knut Verbarg, and Christian Zirkelbach. 1992. Monotonous bisector* trees - a tool for efficient partitioning of complex scenes of geometric objects. Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative. Burkhard Monien and Thomas Ottmann (Eds.), Lecture Notes in Computer Science, Vol. 594, Springer, Berlin, 186\u2013203."},{"key":"e_1_3_4_35_2","doi-asserted-by":"crossref","first-page":"1255","DOI":"10.1145\/1376616.1376748","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008","author":"Pelekis Nikos","year":"2008","unstructured":"Nikos Pelekis, Elias Frentzos, Nikos Giatrakos, and Yannis Theodoridis. 2008. HERMES: Aggregative LBS via a trajectory DB engine. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008. Jason Tsong-Li Wang (Ed.), ACM, 1255\u20131258."},{"key":"e_1_3_4_36_2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIME.2007.59","volume-title":"Proceedings of the14th International Symposium on Temporal Representation and Reasoning (TIME\u201907)","author":"Pelekis Nikos","year":"2007","unstructured":"Nikos Pelekis, Ioannis Kopanakis, Gerasimos Marketos, Irene Ntoutsi, Gennady Andrienko, and Yannis Theodoridis. 2007. Similarity search in trajectory databases. In Proceedings of the14th International Symposium on Temporal Representation and Reasoning (TIME\u201907). 129\u2013140."},{"key":"e_1_3_4_37_2","first-page":"659","volume-title":"Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013.","author":"Pelekis Nikos","year":"2013","unstructured":"Nikos Pelekis, Christos Ntrigkogias, Panagiotis Tampakis, Stylianos Sideridis, and Yannis Theodoridis. 2013. Hermoupolis: A trajectory generator for simulating generalized mobility patterns. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013. Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezn\u00fd (Eds.), Springer, Berlin, 659\u2013662."},{"issue":"1","key":"e_1_3_4_38_2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2782759.2782764","article-title":"Hermoupolis: A semantic trajectory generator in the data science era","volume":"7","author":"Pelekis Nikos","year":"2015","unstructured":"Nikos Pelekis, Stylianos Sideridis, Panagiotis Tampakis, and Yannis Theodoridis. 2015. Hermoupolis: A semantic trajectory generator in the data science era. SIGSPATIAL Special 7, 1 (May2015), 19\u201326.","journal-title":"SIGSPATIAL Special"},{"key":"e_1_3_4_39_2","first-page":"157","volume-title":"Proceedings of the 11th East European Conference on Advances in Databases and Information Systems, ADBIS 2007","volume":"4690","author":"Pola Ives Rene Venturini","year":"2007","unstructured":"Ives Rene Venturini Pola, Caetano Traina Jr., and Agma J. M. Traina. 2007. The MM-Tree: A memory-based metric tree without overlap between nodes. In Proceedings of the 11th East European Conference on Advances in Databases and Information Systems, ADBIS 2007. Lecture Notes in Computer Science, Vol. 4690, Springer, Berlin, 157\u2013171."},{"issue":"3","key":"e_1_3_4_40_2","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/S0146-664X(72)80017-0","article-title":"An iterative procedure for the polygonal approximation of plane curves","volume":"1","author":"Ramer Urs","year":"1972","unstructured":"Urs Ramer. 1972. An iterative procedure for the polygonal approximation of plane curves. Comput. Graph. Image Process. 1, 3 (1972), 244\u2013256.","journal-title":"Comput. Graph. Image Process."},{"key":"e_1_3_4_41_2","first-page":"999","volume-title":"Proceedings of the 2015 IEEE 31st International Conference on Data Engineering","author":"Ranu Sayan","year":"2015","unstructured":"Sayan Ranu, Deepak P, Aditya D. Telang, Prasad Deshpande, and Sriram Raghavan. 2015. Indexing and matching trajectories under inconsistent sampling rates. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. 999\u20131010."},{"issue":"3","key":"e_1_3_4_42_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(91)90233-8","article-title":"Computing the minimum Hausdorff distance between two point sets on a line under translation","volume":"38","author":"Rote G\u00fcnter","year":"1991","unstructured":"G\u00fcnter Rote. 1991. Computing the minimum Hausdorff distance between two point sets on a line under translation. Inform. Process. Lett. 38, 3 (1991), 123\u2013127.","journal-title":"Inform. Process. Lett."},{"key":"e_1_3_4_43_2","first-page":"115","volume-title":"Proceedings of the 6th International Conference on Similarity Search and Applications, SISAP 2013","volume":"8199","author":"Ruiz Guillermo","year":"2013","unstructured":"Guillermo Ruiz, Francisco Santoyo, Edgar Ch\u00e1vez, Karina Figueroa, and Eric Sadit Tellez. 2013. Extreme pivots for faster metric indexes. In Proceedings of the 6th International Conference on Similarity Search and Applications, SISAP 2013. Lecture Notes in Computer Science, Vol. 8199, Springer, Berlin, 115\u2013126."},{"issue":"12","key":"e_1_3_4_44_2","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.14778\/2732977.2732981","article-title":"ClusterJoin: A similarity joins framework using map-reduce","volume":"7","author":"Sarma Akash Das","year":"2014","unstructured":"Akash Das Sarma, Yeye He, and Surajit Chaudhuri. 2014. ClusterJoin: A similarity joins framework using map-reduce. Proc. VLDB Endow. 7, 12 (2014), 1059\u20131070.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_4_45_2","article-title":"Secondo Script for Distributed N-tree Construction","author":"Secondo Script","year":"2023","unstructured":"Secondo Script 2023. Secondo Script for Distributed N-tree Construction. Retrieved December 21, 2023 from https:\/\/secondo-database.github.io\/files\/scripts\/ParallelNTreeConstruction.psec.pdf. .","journal-title":"https:\/\/secondo-database.github.io\/files\/scripts\/ParallelNTreeConstruction.psec.pdf"},{"key":"e_1_3_4_46_2","first-page":"803","volume-title":"Proceedings of the 8th East European Conference on Advances in Databases and Information Systems, ADBIS 2004","author":"Skopal Tom\u00e1s","year":"2004","unstructured":"Tom\u00e1s Skopal, Jaroslav Pokorn\u00fd, and V\u00e1clav Sn\u00e1sel. 2004. PM-tree: Pivoting metric tree for similarity search in multimedia databases. In Proceedings of the 8th East European Conference on Advances in Databases and Information Systems, ADBIS 2004. Springer, Berlin, 803\u2013815."},{"issue":"1","key":"e_1_3_4_47_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00778-019-00574-9","article-title":"A survey of trajectory distance measures and performance evaluation","volume":"29","author":"Su Han","year":"2020","unstructured":"Han Su, Shuncheng Liu, Bolong Zheng, Xiaofang Zhou, and Kai Zheng. 2020. A survey of trajectory distance measures and performance evaluation. VLDB J. 29, 1 (2020), 3\u201332.","journal-title":"VLDB J."},{"issue":"4","key":"e_1_3_4_48_2","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/s00778-005-0178-0","article-title":"The omni-family of all-purpose access methods: A simple and effective way to make similarity search more efficient","volume":"16","author":"Traina Caetano","year":"2007","unstructured":"Caetano Traina, Roberto F. Filho, Agma J. Traina, Marcos R. Vieira, and Christos Faloutsos. 2007. The omni-family of all-purpose access methods: A simple and effective way to make similarity search more efficient. VLDB J. 16, 4 (October2007), 483\u2013505.","journal-title":"VLDB J."},{"issue":"4","key":"e_1_3_4_49_2","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","article-title":"Satisfying general proximity \/ similarity queries with metric trees","volume":"40","author":"Uhlmann Jeffrey K.","year":"1991","unstructured":"Jeffrey K. Uhlmann. 1991. Satisfying general proximity \/ similarity queries with metric trees. Inform. Process. Lett. 40, 4 (1991), 175\u2013179.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"e_1_3_4_50_2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0167-8655(86)90013-9","article-title":"An algorithm for finding nearest neighbours in (approximately) constant average time","volume":"4","author":"Vidal Enrique Ruiz","year":"1986","unstructured":"Enrique Ruiz Vidal. 1986. An algorithm for finding nearest neighbours in (approximately) constant average time. Pattern Recogn. Lett. 4, 3 (July1986), 145\u2013157.","journal-title":"Pattern Recogn. Lett."},{"issue":"5","key":"e_1_3_4_51_2","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0020-0190(95)00161-X","article-title":"Reducing the overhead of the AESA metric-space nearest neighbour searching algorithm","volume":"56","author":"Vilar Juan Miguel","year":"1995","unstructured":"Juan Miguel Vilar. 1995. Reducing the overhead of the AESA metric-space nearest neighbour searching algorithm. Inf. Process. Lett. 56, 5 (December1995), 265\u2013271.","journal-title":"Inf. Process. Lett."},{"key":"e_1_3_4_52_2","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1109\/ICDE.2002.994784","volume-title":"Proceedings of the 18th International Conference on Data Engineering","author":"Vlachos M.","year":"2002","unstructured":"M. Vlachos, G. Kollios, and D. Gunopulos. 2002. Discovering similar multidimensional trajectories. In Proceedings of the 18th International Conference on Data Engineering. 673\u2013684."},{"key":"e_1_3_4_53_2","first-page":"3462","volume-title":"Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017","author":"Wang Xiaosong","year":"2017","unstructured":"Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M. Summers. 2017. ChestX-Ray8: Hospital-scale chest X-Ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases. In Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017. IEEE Computer Society, Washington, DC, USA, 3462\u20133471."},{"key":"e_1_3_4_54_2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1109\/ICDE.1998.655778","volume-title":"Proceedings of the 14th International Conference on Data Engineering","author":"Yi Byoung-Kee","year":"1998","unstructured":"Byoung-Kee Yi, H. V. Jagadish, and C. Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings of the 14th International Conference on Data Engineering. 201\u2013208."},{"key":"e_1_3_4_55_2","volume-title":"Proceedings of the 6th DIMACS Implementation Challenge: Near Neighbor Searches (ALENEX 1999)","author":"Yianilos Peter N.","year":"1999","unstructured":"Peter N. Yianilos, 1999. Excluded middle vantage point forests for nearest neighbor search. In Proceedings of the 6th DIMACS Implementation Challenge: Near Neighbor Searches (ALENEX 1999). E Ch\u00e1vez, G Navarro, and R Baeza-Yates (Eds.)., Baltimore, Maryland, USA."},{"issue":"11","key":"e_1_3_4_56_2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/2934664","article-title":"Apache spark: A unified engine for big data processing","volume":"59","author":"Zaharia Matei","year":"2016","unstructured":"Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, et al.. 2016. Apache spark: A unified engine for big data processing. Commun. ACM 59, 11 (2016), 56\u201365.","journal-title":"Commun. ACM"},{"key":"e_1_3_4_57_2","series-title":"Advances in Database Systems","doi-asserted-by":"crossref","DOI":"10.1007\/0-387-29151-2","volume-title":"Similarity Search - The Metric Space Approach","author":"Zezula Pavel","year":"2006","unstructured":"Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. 2006. Similarity Search - The Metric Space Approach. Advances in Database Systems, Vol. 32. Springer, New York, NY, USA."},{"key":"e_1_3_4_58_2","first-page":"161","volume-title":"Database Technologies 2003, Proceedings of the 14th Australasian Database Conference, ADC 2003 (CRPIT)","volume":"17","author":"Zhou Xiangmin","year":"2003","unstructured":"Xiangmin Zhou, Guoren Wang, Jeffrey Xu Yu, and Ge Yu. 2003. M+-tree: A new dynamical multidimensional index for metric spaces. In Database Technologies 2003, Proceedings of the 14th Australasian Database Conference, ADC 2003 (CRPIT). Vol. 17, Australian Computer Society, Sydney, Australia, 161\u2013168."},{"key":"e_1_3_4_59_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/11408079_36","volume-title":"Proceedings of the 10th International Conference on Database Systems for Advanced Applications, DASFAA 2005","volume":"3453","author":"Zhou Xiangmin","year":"2005","unstructured":"Xiangmin Zhou, Guoren Wang, Xiaofang Zhou, and Ge Yu. 2005. BM \\({}^{\\mbox{+}}\\) -Tree: A hyperplane-based index method for high-dimensional metric spaces. In Proceedings of the 10th International Conference on Database Systems for Advanced Applications, DASFAA 2005, Lecture Notes in Computer Science, Vol. 3453, Springer, New York, NY, USA, 398\u2013409."},{"issue":"4","key":"e_1_3_4_60_2","first-page":"19:1\u201319:42","article-title":"MobilityDB: A mobility database based on PostgreSQL and PostGIS","volume":"45","author":"Zim\u00e1nyi Esteban","year":"2020","unstructured":"Esteban Zim\u00e1nyi, Mahmoud Attia Sakr, and Arthur Lesuisse. 2020. MobilityDB: A mobility database based on PostgreSQL and PostGIS. ACM Trans. Database Syst. 45, 4 (2020), 19:1\u201319:42.","journal-title":"ACM Trans. Database Syst."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716825","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:53Z","timestamp":1750295933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,5]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3716825"],"URL":"https:\/\/doi.org\/10.1145\/3716825","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,5]]},"assertion":[{"value":"2024-08-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}