{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:09Z","timestamp":1787022369399,"version":"build-2736575974"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>\n                    Targeting in-memory one-dimensional search keys, we propose a novel DIstribution-driven Learned Index tree (\n                    <jats:bold>DILI<\/jats:bold>\n                    ), where a concise and computation-efficient linear regression model is used for each node. An internal node's key range is equally divided by its child nodes such that a key search enjoys perfect model prediction accuracy to find the relevant leaf node. A leaf node uses machine learning models to generate searchable data layout and thus accurately predicts the data record position for a key. To construct DILI, we first build a bottom-up tree with linear regression models according to global and local key distributions. Using the bottom-up tree, we build DILI in a top-down manner, individualizing the fanouts for internal nodes according to local distributions. DILI strikes a good balance between the number of leaf nodes and the height of the tree, two critical factors of key search time. Moreover, we design flexible algorithms for DILI to efficiently insert and delete keys and automatically adjust the tree structure when necessary. Extensive experimental results show that DILI outperforms the state-of-the-art alternatives on different kinds of workloads.\n                  <\/jats:p>","DOI":"10.14778\/3598581.3598593","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T18:19:06Z","timestamp":1689013146000},"page":"2212-2224","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["DILI: A Distribution-Driven Learned Index"],"prefix":"10.14778","volume":"16","author":[{"given":"Pengfei","family":"Li","sequence":"first","affiliation":[{"name":"Alibaba Group, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hua","family":"Lu","sequence":"additional","affiliation":[{"name":"Roskilde University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rong","family":"Zhu","sequence":"additional","affiliation":[{"name":"Alibaba Group, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"Alibaba Group, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Long","family":"Yang","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gang","family":"Pan","sequence":"additional","affiliation":[{"name":"Zhejiang University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/github.com\/pfl-cs\/DILI. https:\/\/github.com\/pfl-cs\/DILI."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/www.dropbox.com\/s\/j1d4ufn4fyb4po2\/osm_cellids_800M_uint64.zst?dl=1. https:\/\/www.dropbox.com\/s\/j1d4ufn4fyb4po2\/osm_cellids_800M_uint64.zst?dl=1."},{"key":"e_1_2_1_3_1","unstructured":"https:\/\/www.dropbox.com\/s\/y2u3nbanbnbmg7n\/books_800M_uint64.zst?dl=1. https:\/\/www.dropbox.com\/s\/y2u3nbanbnbmg7n\/books_800M_uint64.zst?dl=1."},{"key":"e_1_2_1_4_1","unstructured":"https:\/\/panthema.net\/2007\/stx-btree. https:\/\/panthema.net\/2007\/stx-btree."},{"key":"e_1_2_1_5_1","unstructured":"https:\/\/github.com\/microsoft\/ALEX. https:\/\/github.com\/microsoft\/ALEX."},{"key":"e_1_2_1_6_1","unstructured":"https:\/\/github.com\/gvinciguerra\/PGM-index. https:\/\/github.com\/gvinciguerra\/PGM-index."},{"key":"e_1_2_1_7_1","unstructured":"https:\/\/github.com\/Jiacheng-WU\/lipp. https:\/\/github.com\/Jiacheng-WU\/lipp."},{"key":"e_1_2_1_8_1","unstructured":"https:\/\/github.com\/learnedsystems\/SOSD. https:\/\/github.com\/learnedsystems\/SOSD."},{"key":"e_1_2_1_9_1","volume-title":"Maria-Florina Balcan and Kilian Q. Weinberger (Eds.)","volume":"48","author":"Acharya Jayadev","year":"2016","unstructured":"Jayadev Acharya , Ilias Diakonikolas , Jerry Li , and Ludwig Schmidt . 2016 . Fast Algorithms for Segmented Regression. In ICML , Maria-Florina Balcan and Kilian Q. Weinberger (Eds.) , Vol. 48 . 2878--2886. Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. 2016. Fast Algorithms for Segmented Regression. In ICML, Maria-Florina Balcan and Kilian Q. Weinberger (Eds.), Vol. 48. 2878--2886."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0094-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733094"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Supawit Chockchowwat. 2022. Tuning Hierarchical Learned Indexes on Disk and Beyond. In SIGMOD. 2515--2517. Supawit Chockchowwat. 2022. Tuning Hierarchical Learned Indexes on Disk and Beyond. In SIGMOD. 2515--2517.","DOI":"10.1145\/3514221.3520255"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_14_1","unstructured":"Intel Corporporation. 2018. Intel 64 and ia-32 architectures software developer manuals. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/articles\/intel-sdm.html. Intel Corporporation. 2018. Intel 64 and ia-32 architectures software developer manuals. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/articles\/intel-sdm.html."},{"key":"e_1_2_1_15_1","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. OpenProceedings.org 407--410. Angjela Davitkova Evica Milchevski and Sebastian Michel. 2020. The ML-Index: A Multidimensional Learned Index for Point Range and Nearest-Neighbor Queries. In EDBT. OpenProceedings.org 407--410."},{"key":"e_1_2_1_16_1","volume-title":"Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska.","author":"Ding Jialin","year":"2020","unstructured":"Jialin Ding , Umar Farooq Minhas , Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska. 2020 . ALEX : An Updatable Adaptive Learned Index. In SIGMOD. 969--984. Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska. 2020. ALEX: An Updatable Adaptive Learned Index. In SIGMOD. 969--984."},{"key":"e_1_2_1_17_1","volume-title":"Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads. CoRR abs\/2006.13282","author":"Ding Jialin","year":"2020","unstructured":"Jialin Ding , Vikram Nathan , Mohammad Alizadeh , and Tim Kraska . 2020 . Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads. CoRR abs\/2006.13282 (2020). arXiv:2006.13282 https:\/\/arxiv.org\/abs\/2006.13282 Jialin Ding, Vikram Nathan, Mohammad Alizadeh, and Tim Kraska. 2020. Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads. CoRR abs\/2006.13282 (2020). arXiv:2006.13282 https:\/\/arxiv.org\/abs\/2006.13282"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_19_1","volume-title":"AMD and VIA CPUs","author":"Fog Agner","year":"2021","unstructured":"Agner Fog . 2018. Lists of Instruction Latencies, Throughputs and Micro-operation Breakdowns for Intel , AMD and VIA CPUs , Technical University of Denmar , Last updated 2021 -01-31. http:\/\/www.agner.org\/optimize\/instruction_tables.pdf,DoA. (2018). Agner Fog. 2018. Lists of Instruction Latencies, Throughputs and Micro-operation Breakdowns for Intel, AMD and VIA CPUs, Technical University of Denmar, Last updated 2021-01-31. http:\/\/www.agner.org\/optimize\/instruction_tables.pdf,DoA. (2018)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Alex Galakatos Michael Markovitch Carsten Binnig Rodrigo Fonseca and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In SIGMOD. 1189--1206. Alex Galakatos Michael Markovitch Carsten Binnig Rodrigo Fonseca and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In SIGMOD. 1189--1206.","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806908"},{"key":"e_1_2_1_22_1","unstructured":"Intel. 2021. Intel Optane Persistent Memory (PMem) Last updated 2021-11-13. https:\/\/www.intel.ca\/content\/www\/ca\/en\/architecture-and-technology\/optane-dcpersistent-memory.html. Intel. 2021. Intel Optane Persistent Memory (PMem) Last updated 2021-11-13. https:\/\/www.intel.ca\/content\/www\/ca\/en\/architecture-and-technology\/optane-dcpersistent-memory.html."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Andreas Kipf Ryan Marcus Alexander van Renen Mihail Stoian Alfons Kemper Tim Kraska and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. In aiDM@SIGMOD. 5:1--5:5. Andreas Kipf Ryan Marcus Alexander van Renen Mihail Stoian Alfons Kemper Tim Kraska and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. In aiDM@SIGMOD. 5:1--5:5.","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_25_1","volume-title":"The art of computer programming","author":"Knuth Donald Ervin","unstructured":"Donald Ervin Knuth . 1997. The art of computer programming . Vol. 3 . Pearson Education . Donald Ervin Knuth. 1997. The art of computer programming. Vol. 3. Pearson Education."},{"key":"e_1_2_1_26_1","volume-title":"Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan.","author":"Kraska Tim","year":"2019","unstructured":"Tim Kraska , Mohammad Alizadeh , Alex Beutel , Ed H. Chi , Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2019 . SageDB: A Learned Database System. In CIDR. Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H. Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2019. SageDB: A Learned Database System. In CIDR."},{"key":"e_1_2_1_27_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska , Alex Beutel , Ed H. Chi , Jeffrey Dean, and Neoklis Polyzotis. 2018 . The Case for Learned Index Structures. In SIGMOD, Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds .). 489--504. Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In SIGMOD, Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). 489--504."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_1_29_1","volume-title":"LISA: A Learned Index Structure for Spatial Data. In SIGMOD. 2119--2133.","author":"Li Pengfei","year":"2020","unstructured":"Pengfei Li , Hua Lu , Qian Zheng , Long Yang , and Gang Pan . 2020 . LISA: A Learned Index Structure for Spatial Data. In SIGMOD. 2119--2133. Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan. 2020. LISA: A Learned Index Structure for Spatial Data. In SIGMOD. 2119--2133."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.08817"},{"key":"e_1_2_1_31_1","unstructured":"David B. Lomet. 1981. Digital B-Trees. In VLDB. 333--344. David B. Lomet. 1981. Digital B-Trees. In VLDB. 333--344."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494141"},{"key":"e_1_2_1_33_1","unstructured":"Yandong Mao Eddie Kohler and Robert Tappan Morris. 2012. Cache craftiness for fast multicore key-value storage. In EuroSys. 183--196. Yandong Mao Eddie Kohler and Robert Tappan Morris. 2012. Cache craftiness for fast multicore key-value storage. In EuroSys. 183--196."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_35_1","unstructured":"Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966). Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Vikram Nathan Jialin Ding Mohammad Alizadeh and Tim Kraska. 2020. Learning Multi-Dimensional Indexes. In SIGMOD. 985--1000. Vikram Nathan Jialin Ding Mohammad Alizadeh and Tim Kraska. 2020. Learning Multi-Dimensional Indexes. In SIGMOD. 985--1000.","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21423"},{"key":"e_1_2_1_39_1","unstructured":"Vladimir Tsymbal. 2019. Tuning Guides and Performance Analysis Papers Last updated 2020-12-15. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/articles\/processor-specific-performance-analysis-papers.html. Vladimir Tsymbal. 2019. Tuning Guides and Performance Analysis Papers Last updated 2020-12-15. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/articles\/processor-specific-performance-analysis-papers.html."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Haixin Wang Xiaoyi Fu Jianliang Xu and Hua Lu. 2019. Learned Index for Spatial Queries. In MDM. 569--574. Haixin Wang Xiaoyi Fu Jianliang Xu and Hua Lu. 2019. Learned Index for Spatial Queries. In MDM. 569--574.","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551848"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547322"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Yingjun Wu Jia Yu Yuanyuan Tian Richard Sidle and Ronald Barber. 2019. Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations. In SIGMOD. 1223--1240. Yingjun Wu Jia Yu Yuanyuan Tian Richard Sidle and Ronald Barber. 2019. Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations. In SIGMOD. 1223--1240.","DOI":"10.1145\/3299869.3319861"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551823"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3598581.3598593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T18:48:41Z","timestamp":1729709321000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3598581.3598593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":45,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.14778\/3598581.3598593"],"URL":"https:\/\/doi.org\/10.14778\/3598581.3598593","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"2023-07-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}