{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:11:59Z","timestamp":1775596319372,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"Dameng Database Research Fund","award":["2025021900057"],"award-info":[{"award-number":["2025021900057"]}]},{"name":"Dameng Database Research Fund","award":["2025021900058"],"award-info":[{"award-number":["2025021900058"]}]},{"name":"National Natural Science Foundation of China","award":["62472293"],"award-info":[{"award-number":["62472293"]}]},{"name":"National Key Research and Development Program of China","award":["2024YFF0617702"],"award-info":[{"award-number":["2024YFF0617702"]}]},{"name":"National Natural Science Foundation of China","award":["U23A20309"],"award-info":[{"award-number":["U23A20309"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U22A2025"],"award-info":[{"award-number":["U22A2025"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62232007"],"award-info":[{"award-number":["62232007"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100013314","name":"111 Project","doi-asserted-by":"crossref","award":["B16009"],"award-info":[{"award-number":["B16009"]}],"id":[{"id":"10.13039\/501100013314","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Similarity search in metric spaces is a fundamental problem in data management with many applications. While numerous indices have been proposed to support similarity search, most existing approaches rely on pivot-based strategies that suffer from critical limitations. Traditional single-pivot methods offer limited pruning power, while multi-pivot techniques often become inefficient as data evolves, since pivot updates incur substantial computational overhead. In this paper, we propose LM-Tree (short for Learned M-Tree), a hybrid learned index that combines pivots and learning models with M-Tree to address the above problems. LM-Tree's key innovation lies in its self-adaptive node architecture, where each node dynamically selects an appropriate number of pivots and incorporates lightweight learning models to enhance pruning efficiency. This design enables each node to maintain a relatively large number of child nodes (or objects for leaf nodes) while consistently delivering strong pruning performance, thereby enabling LM-Tree to use a small number of nodes to index objects in metric spaces. Furthermore, we develop an efficient maintenance algorithm that handles dynamic updates, including pivot adjustments, model reforms, node splits, and merges with low overhead. Extensive experiments on both real and synthetic datasets demonstrate that LM-Tree significantly outperforms state-of-the-art methods.<\/jats:p>","DOI":"10.1145\/3786665","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-0463-5513","authenticated-orcid":false,"given":"Yaqi","family":"Wang","sequence":"first","affiliation":[{"name":"Northeastern University, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2694-1023","authenticated-orcid":false,"given":"Bin","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7033-8643","authenticated-orcid":false,"given":"Rui","family":"Zhu","sequence":"additional","affiliation":[{"name":"Shenyang Aerospace University, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2372-3365","authenticated-orcid":false,"given":"Wenli","family":"Sun","sequence":"additional","affiliation":[{"name":"Northeastern University, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6184-4771","authenticated-orcid":false,"given":"Xiaochun","family":"Yang","sequence":"additional","affiliation":[{"name":"Northeastern University, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534963"},{"key":"e_1_2_1_2_1","first-page":"51","volume-title":"7th International Conference on Extending Database Technology","volume":"1777","author":"Jr Caetano Traina","year":"2000","unstructured":"Caetano Traina Jr., Agma J. M. Traina, Bernhard Seeger, and Christos Faloutsos. Slim-trees: High performance metric trees minimizing overlap between nodes. In Advances in Database Technology - EDBT 2000, 7th International Conference on Extending Database Technology, Konstanz, Germany, March 27-31, 2000, Proceedings, volume 1777, pages 51-65, 2000."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253345"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3206441"},{"key":"e_1_2_1_5_1","first-page":"426","volume-title":"VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece, pages 426-435. Morgan Kaufmann, 1997."},{"key":"e_1_2_1_6_1","volume-title":"8th East European Conference, ADBIS 2004","author":"Skopal Tom\u00e1s","year":"2004","unstructured":"Tom\u00e1s Skopal, Jaroslav Pokorn\u00fd, and V\u00e1clav Sn\u00e1sel. Pm-tree: Pivoting metric tree for similarity search in multimedia databases. In Advances in Databases and Information Systems, 8th East European Conference, ADBIS 2004, Budapest, Hungary, September 22-25, 2004, Local Proceeding, 2004."},{"issue":"1","key":"e_1_2_1_7_1","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 Jun Takada Chino, and Agma J. M. Traina. Dbm-tree: A dynamic metric access method sensitive to local density data. J. Inf. Data Manag., 1(1):111-128, 2010.","journal-title":"J. Inf. Data Manag."},{"key":"e_1_2_1_8_1","first-page":"161","volume-title":"Proceedings of the 14th Australasian Database Conference, ADC 2003, Adelaide, South Australia","volume":"17","author":"Zhou Xiangmin","year":"2003","unstructured":"Xiangmin Zhou, Guoren Wang, Jeffrey Xu Yu, and Ge Yu. M-tree : A new dynamical multidimensional index for metric spaces. In Database Technologies 2003, Proceedings of the 14th Australasian Database Conference, ADC 2003, Adelaide, South Australia, February 2003, volume 17, pages 161-168, 2003."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313789"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0178-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"e_1_2_1_12_1","first-page":"219","volume-title":"Proceedings of the 2002 ACM CIKM International Conference on Information and Knowledge Management, McLean, VA, USA","author":"Jr Caetano Traina","year":"2002","unstructured":"Caetano Traina Jr., Agma J. M. Traina, Roberto F. Santos Filho, and Christos Faloutsos. How to improve the pruning ability of dynamic metric access methods. In Proceedings of the 2002 ACM CIKM International Conference on Information and Knowledge Management, McLean, VA, USA, November 4-9, 2002, pages 219-226. ACM, 2002."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_15_1","first-page":"148","volume-title":"7th East European Conference, ADBIS 2003, Dresden, Germany, September 3-6, 2003","volume":"2798","author":"Skopal Tom\u00e1s","year":"2003","unstructured":"Tom\u00e1s Skopal, Jaroslav Pokorn\u00fd, Michal Kr\u00e1tk\u00fd, and V\u00e1clav Sn\u00e1sel. Revisiting m-tree building principles. In Advances in Databases and Information Systems, 7th East European Conference, ADBIS 2003, Dresden, Germany, September 3-6, 2003, Proceedings, volume 2798, pages 148-162, 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39640-3_42"},{"key":"e_1_2_1_17_1","first-page":"157","volume-title":"11th East European Conference, ADBIS 2007, Varna, Bulgaria, September 29-October 3, 2007","volume":"4690","author":"Venturini Pola Ives Rene","year":"2007","unstructured":"Ives Rene Venturini Pola, Caetano Traina Jr., and Agma J. M. Traina. The mm-tree: A memory-based metric tree without overlap between nodes. In Advances in Databases and Information Systems, 11th East European Conference, ADBIS 2007, Varna, Bulgaria, September 29-October 3, 2007, Proceedings, volume 4690, pages 157-171, 2007."},{"key":"e_1_2_1_18_1","first-page":"398","volume-title":"10th International Conference, DASFAA 2005, Beijing, China, April 17-20, 2005","volume":"3453","author":"Zhou Xiangmin","year":"2005","unstructured":"Xiangmin Zhou, Guoren Wang, Xiaofang Zhou, and Ge Yu. Bm(^mbox, )-tree: A hyperplane-based index method for high-dimensional metric spaces. In Database Systems for Advanced Applications, 10th International Conference, DASFAA 2005, Beijing, China, April 17-20, 2005, Proceedings, volume 3453, pages 398-409, 2005."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2007.06.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115411"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.10.002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673006"},{"key":"e_1_2_1_25_1","volume-title":"7th International Conference Beijing, China","volume":"4487","author":"Mar\u00edn Mauricio","year":"2007","unstructured":"Mauricio Mar\u00edn, Roberto Uribe, and Ricardo J. Barrientos. Searching and updating metric space databases using the parallel EGNAT. In Computational Science - ICCS 2007, 7th International Conference Beijing, China, May 27-30, 2007, Proceedings, Part I, volume 4487 of Lecture Notes in Computer Science, pages 229-236. Springer, 2007."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551823"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00329"},{"key":"e_1_2_1_28_1","first-page":"1189","volume-title":"SIGMOD","author":"Galakatos Alex","year":"2019","unstructured":"Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. FITing-Tree: A data-aware index structure. In SIGMOD, pages 1189-1206, 2019."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470892"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/588011.588037"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_36_1","first-page":"193","volume-title":"Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA]","author":"Yang Zongheng","year":"2020","unstructured":"Zongheng Yang, Badrish Chandramouli, Chi Wang, Johannes Gehrke, Yinan Li, Umar Farooq Minhas, Per-\u00c5ke Larson, Donald Kossmann, and Rajeev Acharya. Qd-tree: Learning data layouts for big data analytics. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 193-208. ACM, 2020."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72617-0_17"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588917"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551800"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589332"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:03:49Z","timestamp":1775592229000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786665"],"URL":"https:\/\/doi.org\/10.1145\/3786665","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}