{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:17Z","timestamp":1781326697618,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"the National Key Research and Development Program of China","award":["2023YFB4503600"],"award-info":[{"award-number":["2023YFB4503600"]}]},{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62472311"],"award-info":[{"award-number":["62472311"]}],"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":"publisher","award":["U23A20299"],"award-info":[{"award-number":["U23A20299"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Postdoctoral Fellowship Program of CPSF","award":["GZC20251051"],"award-info":[{"award-number":["GZC20251051"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>The first generation of learned indexes inherently achieved lower space overhead than traditional index structures, establishing this advantage as one of the pivotal research directions in index optimization. However, in their pursuit of peak performance, designers often significantly increase space overhead, which becomes infeasible in scenarios with limited storage space. Furthermore, the design of current learned indexes optimized for time-space tradeoff is flawed, as they collapse catastrophically under prevalent dense or duplicate insertion workloads. To address these challenges, we first quantitatively analyze the time-space correlation characteristics of learned indexes from a theoretical perspective and identify the core influencing factors. Based on this, time-space cost minimization function models are established and an updatable learned index framework, LIFT, is constructed. Furthermore, LIFT incorporates specifically designed structural adjustment mechanisms to effectively counter existing poisoning attacks, significantly enhancing index robustness without increasing time-space cost. Evaluation results demonstrate that LIFT consistently achieves the optimal time-space tradeoff across various workloads and datasets, outperforming all other state-of-the-art indexes.<\/jats:p>","DOI":"10.1145\/3769800","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0886-8713","authenticated-orcid":false,"given":"Hui","family":"Wang","sequence":"first","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University, Tianjin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9651-0651","authenticated-orcid":false,"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University, Tianjin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4644-0733","authenticated-orcid":false,"given":"Jiake","family":"Ge","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University, Tianjin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3286-9259","authenticated-orcid":false,"given":"Yunpeng","family":"Chai","sequence":"additional","affiliation":[{"name":"School of Information, Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9700-5809","authenticated-orcid":false,"given":"Lei","family":"Liang","sequence":"additional","affiliation":[{"name":"Unaffiliated, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5369-6821","authenticated-orcid":false,"given":"Peng","family":"Yi","sequence":"additional","affiliation":[{"name":"Unaffiliated, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397536.3426358"},{"key":"e_1_2_1_2_1","volume-title":"Learned Indexes with Distribution Smoothing via Virtual Points. CoRR","author":"Amarasinghe Kasun","year":"2024","unstructured":"Kasun Amarasinghe, Farhana Choudhury, Jianzhong Qi, and James Bailey. 2024. Learned Indexes with Distribution Smoothing via Virtual Points. CoRR (2024)."},{"key":"e_1_2_1_3_1","unstructured":"AWS. 2010. OpenStreetMap database. https:\/\/aws.amazon.com\/public-datasets\/osm."},{"key":"e_1_2_1_4_1","volume-title":"https:\/\/panthema.net\/2007\/stx-btree\/, retrieved","author":"Bingmann Timo","year":"2021","unstructured":"Timo Bingmann. 2013. STX B Tree 0.9. https:\/\/panthema.net\/2007\/stx-btree\/, retrieved Sep. 1, 2021.."},{"key":"e_1_2_1_5_1","first-page":"407","article-title":"The ML-Index: A Multidimensional, Learned Index for Point, Range, and Nearest-Neighbor Queries","author":"Davitkova Angjela","year":"2020","unstructured":"Angjela Davitkova, Evica Milchevski, and Sebastian Michel. 2020. The ML-Index: A Multidimensional, Learned Index for Point, Range, and Nearest-Neighbor Queries.. In EDBT. 407-410.","journal-title":"EDBT."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00201"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_10_1","unstructured":"K Fraser. 2004. Practical lock-freedom (Doctoral dissertation University of Cambridge). (2004)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00031"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626752"},{"key":"e_1_2_1_14_1","first-page":"203","volume-title":"Foundations and Trends\u00ae in Databases","volume":"3","author":"Goetz","year":"2011","unstructured":"Goetz Graefe et al., 2011. Modern B-tree techniques. Foundations and Trends\u00ae in Databases, Vol. 3, 4 (2011), 203-402."},{"key":"e_1_2_1_15_1","first-page":"169","volume-title":"More Modern B-Tree Techniques. Foundations and Trends\u00ae in Databases","volume":"13","author":"Goetz","year":"2024","unstructured":"Goetz Graefe et al., 2024. More Modern B-Tree Techniques. Foundations and Trends\u00ae in Databases, Vol. 13, 3 (2024), 169-249."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588917"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3390\/math10234507"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389752"},{"key":"e_1_2_1_21_1","first-page":"1","volume-title":"Updatable Learned Indexes Meet Disk-Resident DBMS-From Evaluations to Design Choices. Proceedings of the ACM on Management of Data","volume":"1","author":"Lan Hai","year":"2023","unstructured":"Hai Lan, Zhifeng Bao, J Shane Culpepper, and Renata Borovica-Gajic. 2023. Updatable Learned Indexes Meet Disk-Resident DBMS-From Evaluations to Design Choices. Proceedings of the ACM on Management of Data, Vol. 1, 2 (2023), 1-22."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598593"},{"key":"e_1_2_1_26_1","volume-title":"https:\/\/libraries.io\/data","author":"Repository","year":"2017","unstructured":"Libraries.io. 2017. Repository ID. (2017). https:\/\/libraries.io\/data."},{"key":"e_1_2_1_27_1","unstructured":"LIFT. 2025. Appendix. https:\/\/github.com\/WHIndex\/lift_appendix."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-021-00825-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494141"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570704"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"R Marcus M Stoian A Kipf S Misra A van Renen A Kemper T Neumann and T Kraska. 2021. Benchmarking learned indexes. (2021).","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464509.3464886"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2014.11.021"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589332"},{"key":"e_1_2_1_37_1","volume-title":"Towards practical learned indexing. arXiv preprint arXiv:2108.05117","author":"Stoian Mihail","year":"2021","unstructured":"Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. 2021. Towards practical learned indexing. arXiv preprint arXiv:2108.05117 (2021)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3206441"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611520"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681981"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533579"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551848"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547322"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626742"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636232"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-022-01021-6"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551823"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654948"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470892"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503646.3524295"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:42:42Z","timestamp":1781325762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769800"],"URL":"https:\/\/doi.org\/10.1145\/3769800","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}