{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T16:08:54Z","timestamp":1778947734059,"version":"3.51.4"},"reference-count":156,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62102351, 62025206 and 61972338"],"award-info":[{"award-number":["62102351, 62025206 and 61972338"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004731","name":"Zhejiang Provincial Natural Science Foundation","doi-asserted-by":"crossref","award":["LR21F020005"],"award-info":[{"award-number":["LR21F020005"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DIREC"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>With the continued digitization of societal processes, we are seeing an explosion in available data. This is referred to as big data. In a research setting, three aspects of the data are often viewed as the main sources of challenges when attempting to enable value creation from big data: volume, velocity, and variety. Many studies address volume or velocity, while fewer studies concern the variety. Metric spaces are ideal for addressing variety because they can accommodate any data as long as it can be equipped with a distance notion that satisfies the triangle inequality. To accelerate search in metric spaces, a collection of indexing techniques for metric data have been proposed. However, existing surveys offer limited coverage, and a comprehensive empirical study exists has yet to be reported. We offer a comprehensive survey of existing metric indexes that support exact similarity search: we summarize existing partitioning, pruning, and validation techniques used by metric indexes to support exact similarity search; we provide the time and space complexity analyses of index construction; and we offer an empirical comparison of their query processing performance. Empirical studies are important when evaluating metric indexing performance, because performance can depend highly on the effectiveness of available pruning and validation as well as on the data distribution, which means that complexity analyses often offer limited insights. This article aims at revealing strengths and weaknesses of different indexing techniques to offer guidance on selecting an appropriate indexing technique for a given setting, and to provide directions for future research on metric indexing.<\/jats:p>","DOI":"10.1145\/3534963","type":"journal-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T08:51:27Z","timestamp":1653295887000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Indexing Metric Spaces for Exact Similarity Search"],"prefix":"10.1145","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5685-7017","authenticated-orcid":false,"given":"Lu","family":"Chen","sequence":"first","affiliation":[{"name":"College of Computer Science, Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3816-8450","authenticated-orcid":false,"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"College of Computer Science, Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4337-3953","authenticated-orcid":false,"given":"Xuan","family":"Song","sequence":"additional","affiliation":[{"name":"College of Computer Science, Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8417-4926","authenticated-orcid":false,"given":"Zheng","family":"Li","sequence":"additional","affiliation":[{"name":"College of Computer Science, Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4555-6232","authenticated-orcid":false,"given":"Yifan","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Computer Science, Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8632-1539","authenticated-orcid":false,"given":"Xiaoye","family":"Miao","sequence":"additional","affiliation":[{"name":"Center for Data Science, Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9697-7670","authenticated-orcid":false,"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aalborg University, Aalborg, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375668"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871622"},{"issue":"3","key":"e_1_3_3_4_2","first-page":"375","article-title":"DAHC-tree: An effective index for approximate search in high-dimensional metric spaces","volume":"1","author":"Almeida Jurandy","year":"2010","unstructured":"Jurandy Almeida, Eduardo Valle, Ricardo da S. Torres, and Neucimar J. Leite. 2010. DAHC-tree: An effective index for approximate search in high-dimensional metric spaces. Journal of Information and Data Management 1, 3 (2010), 375\u2013390.","journal-title":"Journal of Information and Data Management"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-012-1271-1"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975673.21"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.93"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164206"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2009.21"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32153-5_6"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2007.06.001"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1140"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497441"},{"key":"e_1_3_3_14_2","first-page":"331","article-title":"Searching: An algorithmic tour","volume":"37","author":"Baeza-Yates Ricardo","year":"1997","unstructured":"Ricardo Baeza-Yates. 1997. Searching: An algorithmic tour. Encyclopedia of Computer Science and Technology 37 (1997), 331\u2013359.","journal-title":"Encyclopedia of Computer Science and Technology"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/647814.738307"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1862344.1862351"},{"key":"e_1_3_3_17_2","first-page":"322","volume-title":"Proceedings of the SIGMOD Record","volume":"19","author":"Beckmann Norbert","year":"1990","unstructured":"Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The \\( \\rm R^* \\) -tree: An efficient and robust access method for points and rectangles. In Proceedings of the SIGMOD Record, Vol. 19. 322\u2013331."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49257-7_15"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253345"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/328939.328959"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-010-0614-z"},{"key":"e_1_3_3_24_2","unstructured":"Sergey Brin. 1995. Near neighbor search in large metric spaces. In Proceedings of the 21th International Conference on Very Large Data Bases (1995) 574\u2013584."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32153-5_9"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/362003.362025"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(03)00065-5"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1178677.1178698"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.53"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.06.004"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03973-7_18"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70815"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.10.014"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878182"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2004.11.014"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2506556"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723728"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115411"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0465-6"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324916000334"},{"key":"e_1_3_3_43_2","first-page":"15","volume-title":"Proceedings of the 9th Australasian Database Conference","author":"Ciaccia Paolo","year":"1998","unstructured":"Paolo Ciaccia and Marco Patella. 1998. Bulk loading the M-tree. In Proceedings of the 9th Australasian Database Conference. 15\u201326."},{"key":"e_1_3_3_44_2","volume-title":"Proceedings of the DELOS Workshop","author":"Ciaccia Paolo","year":"2000","unstructured":"Paolo Ciaccia and Marco Patella. 2000. The \\( \\rm M^2 \\) -tree: Processing complex multi-feature queries with just one index. In Proceedings of the DELOS Workshop."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/582410.582412"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68474-1_1"},{"key":"e_1_3_3_47_2","first-page":"426","volume-title":"Proceedings of the VLDB","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 Proceedings of the VLDB. 426\u2013435."},{"key":"e_1_3_3_48_2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","article-title":"Nearest-neighbor searching and metric space dimensions","author":"Clarkson Kenneth L.","year":"2006","unstructured":"Kenneth L. Clarkson . 2006. Nearest-neighbor searching and metric space dimensions. In Nearest-neighbor Methods for Learning and Vision: Theory and Practice (2006), 15\u201359.","journal-title":"Nearest-neighbor Methods for Learning and Vision: Theory and Practice"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46759-7_5"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3001583"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02224-2_3"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2018.01.002"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(87)90041-X"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.5555\/49539.49551"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30192-9_13"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025026030880"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45227-0_48"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_26"},{"issue":"6","key":"e_1_3_3_60_2","first-page":"3","article-title":"Speeding up spatial approximation search in metric spaces","volume":"14","author":"Figueroa Karina","year":"2010","unstructured":"Karina Figueroa, Edgar Ch\u00e1vez, Gonzalo Navarro, and Rodrigo Paredes. 2010. Speeding up spatial approximation search in metric spaces. Journal of Experimental Algorithmics 14, 6 (2010), 3\u20136.","journal-title":"Journal of Experimental Algorithmics"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32047-8_14"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498318"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.5555\/1090380.1710897"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2006.06.012"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00010672"},{"key":"e_1_3_3_66_2","first-page":"429","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases","author":"Goldstein Jonathan","year":"2000","unstructured":"Jonathan Goldstein and Raghu Ramakrishnan. 2000. Contrast plots and p-sphere trees: Space vs. time in nearest neighbour searches. In Proceedings of the 26th International Conference on Very Large Data Bases. 429\u2013440."},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03625-5_9"},{"issue":"1","key":"e_1_3_3_68_2","first-page":"165","article-title":"Ptolemaic indexing","volume":"6","author":"Hetland Magnus Lie","year":"2015","unstructured":"Magnus Lie Hetland. 2015. Ptolemaic indexing. Journal of Computational Geometry 6, 1 (2015), 165\u2013184.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2012.05.011"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2013.139"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68474-1_5"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68474-1_6"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60936-8_19"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41062-8_3"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45151-X_34"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39640-3_42"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.235263"},{"key":"e_1_3_3_80_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.79"},{"key":"e_1_3_3_81_2","volume-title":"Proceedings of the CIIA","author":"Kouahla Zineddine","year":"2011","unstructured":"Zineddine Kouahla. 2011. Exploring intersection trees for indexing metric spaces. In Proceedings of the CIIA."},{"key":"e_1_3_3_82_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2001.937632"},{"key":"e_1_3_3_83_2","doi-asserted-by":"publisher","DOI":"10.5555\/615204.615210"},{"key":"e_1_3_3_84_2","doi-asserted-by":"publisher","DOI":"10.1007\/11795131_64"},{"key":"e_1_3_3_85_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.01.007"},{"key":"e_1_3_3_86_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_3_3_87_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.10.004"},{"key":"e_1_3_3_88_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72584-8_30"},{"key":"e_1_3_3_89_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32597-7_41"},{"key":"e_1_3_3_90_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68474-1_4"},{"key":"e_1_3_3_91_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(96)00032-3"},{"key":"e_1_3_3_92_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)90095-7"},{"key":"e_1_3_3_93_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.01.009"},{"key":"e_1_3_3_94_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-021-00173-1"},{"key":"e_1_3_3_95_2","doi-asserted-by":"publisher","DOI":"10.1145\/1995412.1995418"},{"key":"e_1_3_3_96_2","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824059"},{"key":"e_1_3_3_97_2","first-page":"331","volume-title":"Proceedings of the VLDB","author":"Nanopoulos Alexandros","year":"2001","unstructured":"Alexandros Nanopoulos, Yannis Theodoridis, and Yannis Manolopoulos. 2001. C2P: Clustering based on closest pairs. In Proceedings of the VLDB. 331\u2013340."},{"key":"e_1_3_3_98_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.1999.796589"},{"key":"e_1_3_3_99_2","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200060"},{"key":"e_1_3_3_100_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.06.004"},{"key":"e_1_3_3_101_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCCC.2001.972650"},{"key":"e_1_3_3_102_2","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694958"},{"key":"e_1_3_3_103_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCCC.2003.1245441"},{"key":"e_1_3_3_104_2","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2009.28"},{"key":"e_1_3_3_105_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.03.009"},{"key":"e_1_3_3_106_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2011.01.002"},{"key":"e_1_3_3_107_2","doi-asserted-by":"crossref","unstructured":"Hartmut Noltemeier Knut Verbarg and Christian Zirkelbach. 1992. Monotonous bisector \\( ^* \\) trees\u2014a tool for efficient partitioning of complex scenes of geometric objects. In Proceedings of Data Structures and Efficient Algorithms Final Report on DFG Special Joint Initiative . 186\u2013203.","DOI":"10.1007\/3-540-55488-2_27"},{"key":"e_1_3_3_108_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.10.002"},{"key":"e_1_3_3_109_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49214-7_2"},{"key":"e_1_3_3_110_2","first-page":"131","volume-title":"Proceedings of the Brazilian Symposium on Databases","author":"Ocsa Alexander","year":"2007","unstructured":"Alexander Ocsa, Carlos Bedregal, and Ernesto Cuadros-Vargas. 2007. A new approach for similarity queries using neighborhood graphs. In Proceedings of the Brazilian Symposium on Databases. 131\u2013142."},{"key":"e_1_3_3_111_2","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_14"},{"key":"e_1_3_3_112_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69507-3_37"},{"key":"e_1_3_3_113_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.10.002"},{"key":"e_1_3_3_114_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75185-4_13"},{"key":"e_1_3_3_115_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989431"},{"key":"e_1_3_3_116_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10559-017-9966-y"},{"key":"e_1_3_3_117_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32047-8_2"},{"key":"e_1_3_3_118_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02224-2_9"},{"key":"e_1_3_3_119_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_3_3_120_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(86)90013-9"},{"key":"e_1_3_3_121_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41062-8_12"},{"key":"e_1_3_3_122_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25087-8_26"},{"key":"e_1_3_3_123_2","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166077"},{"key":"e_1_3_3_124_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-27615-7_8"},{"key":"e_1_3_3_125_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02224-2_2"},{"key":"e_1_3_3_126_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11988-5_8"},{"key":"e_1_3_3_127_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75185-4_14"},{"key":"e_1_3_3_128_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85654-2_30"},{"key":"e_1_3_3_129_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.013"},{"key":"e_1_3_3_130_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39403-7_13"},{"key":"e_1_3_3_131_2","first-page":"803","volume-title":"Proceedings of the East European Conference on Advances in Databases and Information Systems","author":"Skopal Tom\u00e1s","year":"2004","unstructured":"Tom\u00e1s Skopal, Jaroslav Pokorn\u1ef3, and Vaclav Snasel. 2004. PM-tree: Pivoting metric tree for similarity search in multimedia databases. In Proceedings of the East European Conference on Advances in Databases and Information Systems. 803\u2013815."},{"key":"e_1_3_3_132_2","doi-asserted-by":"publisher","DOI":"10.1145\/3226595.3226636"},{"key":"e_1_3_3_133_2","doi-asserted-by":"publisher","DOI":"10.1145\/3226595.3226637"},{"key":"e_1_3_3_134_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-019-01348-1"},{"key":"e_1_3_3_135_2","doi-asserted-by":"publisher","DOI":"10.5555\/1151699.1151709"},{"key":"e_1_3_3_136_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46439-5_4"},{"key":"e_1_3_3_137_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0178-0"},{"key":"e_1_3_3_138_2","first-page":"219","volume-title":"Proceedings of the 11th International Conference on Information and Knowledge Management","author":"Jr Caetano Traina","year":"2002","unstructured":"Caetano Traina Jr, Agma Traina, Roberto Santos Filho, and Christos Faloutsos. 2002. How to improve the pruning ability of dynamic metric access methods. In Proceedings of the 11th International Conference on Information and Knowledge Management. 219\u2013226."},{"key":"e_1_3_3_139_2","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(91)90146-M"},{"key":"e_1_3_3_140_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_3_3_141_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32047-8_4"},{"key":"e_1_3_3_142_2","doi-asserted-by":"publisher","DOI":"10.1145\/2000486.2000490"},{"key":"e_1_3_3_143_2","first-page":"163","volume-title":"Proceedings of the SBBD","author":"Vieira Marcos R.","year":"2004","unstructured":"Marcos R. Vieira, Caetano Traina Jr, Fabio J. T. Chino, and Agma J. M. Traina. 2004. DBM-tree: A dynamic metric access method sensitive to local density data. In Proceedings of the SBBD. 163\u2013177."},{"issue":"1","key":"e_1_3_3_144_2","first-page":"111","article-title":"DBM-tree: A dynamic metric access method sensitive to local density data","volume":"1","author":"Vieira Marcos R.","year":"2010","unstructured":"Marcos R. Vieira, Caetano Traina Jr, Fabio J. T. Chino, and Agma J. M. Traina. 2010. DBM-tree: A dynamic metric access method sensitive to local density data. Journal of Information and Data Management 1, 1 (2010), 111\u2013111.","journal-title":"Journal of Information and Data Management"},{"key":"e_1_3_3_145_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00161-X"},{"key":"e_1_3_3_146_2","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2009.9"},{"key":"e_1_3_3_147_2","first-page":"194","volume-title":"Proceedings of the VLDB","author":"Weber Roger","year":"1998","unstructured":"Roger Weber, Hans-J\u00f6rg Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of the VLDB. 194\u2013205."},{"key":"e_1_3_3_148_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2164-16-S3-S5"},{"key":"e_1_3_3_149_2","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.2017EDP7077"},{"key":"e_1_3_3_150_2","first-page":"311","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms","volume":"66","author":"Yianilos Peter N","year":"1993","unstructured":"Peter N Yianilos. 1993. Data structures and algorithms for nearest neighbor. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 66. 311."},{"key":"e_1_3_3_151_2","volume-title":"Proceedings of the ALENEX","author":"Yianilos Peter N.","year":"1999","unstructured":"Peter N. Yianilos. 1999. Excluded middle vantage point forests for nearest neighbor search. In Proceedings of the ALENEX."},{"key":"e_1_3_3_152_2","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-29151-2"},{"key":"e_1_3_3_153_2","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050069"},{"key":"e_1_3_3_154_2","doi-asserted-by":"publisher","DOI":"10.5555\/3225646.3225859"},{"key":"e_1_3_3_155_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807266"},{"key":"e_1_3_3_156_2","first-page":"161","volume-title":"Proceedings of the 14th Australasian Database Conference","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 Proceedings of the 14th Australasian Database Conference. 161\u2013168."},{"key":"e_1_3_3_157_2","doi-asserted-by":"publisher","DOI":"10.1007\/11408079_36"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3534963","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3534963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:54Z","timestamp":1750186974000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3534963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,7]]},"references-count":156,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3534963"],"URL":"https:\/\/doi.org\/10.1145\/3534963","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,7]]},"assertion":[{"value":"2020-11-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}