{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T20:26:19Z","timestamp":1782937579956,"version":"3.54.5"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2023YFB4502400"],"award-info":[{"award-number":["2023YFB4502400"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>Learned indexes, which model key-value data structures by machine learning models, have been extensively studied. However, the fastest immutable learned indexes (e.g., RMI) do not provide the same tight lookup bounds as classical indexes such as B-trees. There are learned indexes that provide tight bounds (e.g., PGM) but those fall short in query performance. This gives rise to an interesting open question: whether there exists a learned index that simultaneously achieves state-of-the-art empirical performance and matching complexity?<\/jats:p>\n                  <jats:p>In this paper, we give a positive answer to this standing problem.We propose two new online model-building policies: (1) simplifying distribution by the adoption of a proper granularity (i.e., grouping multiple keys together for model-building) and (2) actively tuning distribution through key repositioning. Additionally, we introduce a general framework that combines these two policies for performance optimization under a given memory budget. We put everything together to design VEGA, a learned index that simultaneously achieves competitive theoretical and empirical performance compared to state-of-the-art learned indexes. We conducted extensive evaluations, demonstrating VEGA achieves both better lookup and building performance.<\/jats:p>","DOI":"10.1145\/3709736","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5764-960X","authenticated-orcid":false,"given":"Meng","family":"Li","sequence":"first","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9322-1114","authenticated-orcid":false,"given":"Huayi","family":"Chai","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8197-0903","authenticated-orcid":false,"given":"Siqiang","family":"Luo","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0545-8187","authenticated-orcid":false,"given":"Haipeng","family":"Dai","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1565-9997","authenticated-orcid":false,"given":"Rong","family":"Gu","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8403-9655","authenticated-orcid":false,"given":"Jiaqi","family":"Zheng","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6934-1685","authenticated-orcid":false,"given":"Guihai","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Lyric Doshi, Tim Kraska, Andy Ly, Christopher Olston, et al.","author":"Abu-Libdeh Hussam","year":"2020","unstructured":"Hussam Abu-Libdeh, Deniz Altinb\u00fcken, Alex Beutel, Ed H Chi, Lyric Doshi, Tim Kraska, Andy Ly, Christopher Olston, et al. 2020. Learned indexes for a google-scale disk-based database. arXiv preprint arXiv:2012.12501 (2020)."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 1970 ACM SIGFIDET Workshop on Data Description, Access and Control. Association for Computing Machinery, 107--141","author":"Bayer R.","unstructured":"R. Bayer and E. McCreight. 1970. Organization and Maintenance of Large Ordered Indices. In Proceedings of the 1970 ACM SIGFIDET Workshop on Data Description, Access and Control. Association for Computing Machinery, 107--141."},{"key":"e_1_2_1_3_1","volume-title":"Software Pioneers: Contributions to Software Engineering","author":"Bayer R.","unstructured":"R. Bayer and E. McCreight. 2002. Organization and Maintenance of Large Ordered Indexes. In Software Pioneers: Contributions to Software Engineering, Manfred Broy and Ernst Denert (Eds.). Springer Berlin Heidelberg, 245--262."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502521"},{"key":"e_1_2_1_5_1","unstructured":"Timo Bingmann. 2007. STX B Tree C Template Classes. https:\/\/panthema.net\/2007\/stx-btree\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80075-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13960-9_8"},{"key":"e_1_2_1_8_1","volume-title":"Information Technology","volume":"59","author":"Broneske David","year":"2017","unstructured":"David Broneske and Gunter Saake. 2017. Exploiting capabilities of modern processors in data intensive applications. Information Technology, Vol. 59 (2017)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375688"},{"key":"e_1_2_1_10_1","volume-title":"USENIX Symposium on Operating Systems Design and Implementation. USENIX, 155--171","author":"Dai Yifan","year":"2020","unstructured":"Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2020. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In USENIX Symposium on Operating Systems Design and Implementation. USENIX, 155--171."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_13_1","unstructured":"Paolo Ferragina and Giorgio Vinciguerra. 2021. PGM source code. https:\/\/pgm.di.unipi.it\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626752"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP52444.2021.9651956"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466826.3466842"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659439"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517867"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589284"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00369"},{"key":"e_1_2_1_25_1","volume-title":"Carey","author":"Lehman Tobin J.","year":"1986","unstructured":"Tobin J. Lehman and Michael J. Carey. 1986. A Study of Index Structures for Main Memory Database Management Systems. In Proceedings of the International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc., 294--303."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598593"},{"key":"e_1_2_1_29_1","unstructured":"Yaliang Li Daoyuan Chen Bolin Ding Kai Zeng and Jingren Zhou. 2021a. A Pluggable Learned Index Method via Sampling and Gap Insertion. arxiv: 2101.00808"},{"key":"e_1_2_1_30_1","first-page":"3","article-title":"FILM","volume":"16","author":"Ma Chaohong","year":"2022","unstructured":"Chaohong Ma, Xiaohui Yu, Yifan Li, Xiaofeng Meng, and Aishan Maoliniyazi. 2022. FILM: A Fully Learned Index for Larger-Than-Memory Databases. Proc. VLDB Endow., Vol. 16, 3 (nov 2022), 561--573.","journal-title":"A Fully Learned Index for Larger-Than-Memory Databases. Proc. VLDB Endow."},{"key":"e_1_2_1_31_1","unstructured":"Marcel Maltry and Jens Dittrich. 2021. A Critical Analysis of Recursive Model Indexes. arxiv: arXiv:2106.16166"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384706"},{"key":"e_1_2_1_35_1","first-page":"9","article-title":"An On-Line Algorithm for Fitting Straight Lines between Data","volume":"24","author":"O'Rourke Joseph","year":"1981","unstructured":"Joseph O'Rourke. 1981. An On-Line Algorithm for Fitting Straight Lines between Data Ranges. Commun. ACM, Vol. 24, 9 (sep 1981), 574--578.","journal-title":"Ranges. Commun. ACM"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc., 78--89","author":"Rao Jun","unstructured":"Jun Rao and Kenneth A. Ross. 1999. Cache Conscious Indexing for Decision-Support in Main Memory. In Proceedings of the 25th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc., 78--89."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, 475--486","author":"Rao Jun","unstructured":"Jun Rao and Kenneth A. Ross. 2000. Making B- Trees Cache Conscious in Main Memory. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, 475--486."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405886"},{"key":"e_1_2_1_39_1","volume-title":"Searching in sorted lists on modern processors. Bachelor's thesis","author":"Schulz Lars-Christian","unstructured":"Lars-Christian Schulz. 2017. Searching in sorted lists on modern processors. Bachelor's thesis, University of Magdeburg (2017)."},{"key":"e_1_2_1_40_1","unstructured":"Mihail Stoian Andreas Kipf Ryan Marcus and Tim Kraska. 2021. Towards Practical Learned Indexing. arxiv: arXiv:2108.05117"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5120\/2418-3233"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Chuzhe Tang Youyun Wang Zhiyuan Dong Gansen Hu Zhaoguo Wang Minjie Wang and Haibo Chen. 2020a. XIndex: a scalable learned index for multicore data storage. In PPoPP. ACM 308--320.","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_44_1","volume-title":"Communications in Computer and Information Science","author":"Wallewein-Eising Marten","unstructured":"Marten Wallewein-Eising, David Broneske, and Gunter Saake. 2018. SIMD Acceleration for Main-Memory Index Structures--A Survey. In Communications in Computer and Information Science. Springer, 105--119."},{"key":"e_1_2_1_45_1","unstructured":"Wikipedia. 2023. SIMD Instructions. https:\/\/en.wikipedia.org\/wiki\/Single_instruction _multiple_data"},{"key":"e_1_2_1_46_1","unstructured":"Wikipedia. 2024a. Bimodal Distribution. https:\/\/simple.wikipedia.org\/wiki\/Bimodal_distribution"},{"key":"e_1_2_1_47_1","unstructured":"Wikipedia. 2024b. Zipf Distribution. https:\/\/en.wikipedia.org\/wiki\/Zipf%27s_law"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551848"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547322"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303955"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247643"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.55846\/9789675492860"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483551"},{"key":"e_1_2_1_55_1","first-page":"97","article-title":"Adapting Tree Structures for Processing with SIMD Instructions","volume":"14","author":"Zeuch Steffen","year":"2014","unstructured":"Steffen Zeuch, Johann-Christoph Freytag, and Frank Huber. 2014. Adapting Tree Structures for Processing with SIMD Instructions.. In EDBT, Vol. 14. 97--108.","journal-title":"EDBT"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551823"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654954"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:16:49Z","timestamp":1774981009000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709736"],"URL":"https:\/\/doi.org\/10.1145\/3709736","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}