{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T00:15:32Z","timestamp":1787530532824,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Institute for Information and Communications Technology Planning and Evaluation","award":["2022-0-01022, 2021-0-01475"],"award-info":[{"award-number":["2022-0-01022, 2021-0-01475"]}]},{"DOI":"10.13039\/501100006374","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2022R1A2C1006050"],"award-info":[{"award-number":["2022R1A2C1006050"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>By embedding the distribution of keys in indexing structure, learned indexes can minimize the index size and maximize the lookup performance. Yet, one of the problems in the present learned index is the long index-building time. The conventional learned index requires a complete traversal of the entire dataset, which makes it less practical than traditional index. This paper challenges the efficiency of build time to make the learned index practical.<\/jats:p>\n          <jats:p>Our approach for a build time-efficient learned index is to employ sampled learning. In this paper, we present two error-bounded sampling schemes: Sample EB-PLA, and Sample EB-Histogram. Although sampling is a simple idea, there are several considerations to make it practical. For example, sampling interval, error-boundness, and index hyper-parameters are inter-related each other, presenting complicated trade-offs between build-time, index size, accuracy and lookup latency.<\/jats:p>\n          <jats:p>Throughout the extensive experiments over six real-world datasets, we show that the index-building time can be efficiently reduced over an order of magnitude by our sampling schemes. The results reveal that the sampling expands the design space of learned indexes, including the build-time as well as lookup performance and index size. Our Pareto analysis shows that a learned index can be built more efficiently than a traditional index through sampling.<\/jats:p>","DOI":"10.1145\/3654919","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-25","source":"Crossref","is-referenced-by-count":6,"title":["Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-4030-9344","authenticated-orcid":false,"given":"Minguk","family":"Choi","sequence":"first","affiliation":[{"name":"Dankook University, Yongin, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5464-4619","authenticated-orcid":false,"given":"Seehwan","family":"Yoo","sequence":"additional","affiliation":[{"name":"Dankook University, Yongin, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2042-6327","authenticated-orcid":false,"given":"Jongmoo","family":"Choi","sequence":"additional","affiliation":[{"name":"Dankook University, Yongin, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2007. STX B-Tree. Retrieved October 14 2023 from https:\/\/panthema.net\/2007\/stx-btree\/"},{"key":"e_1_2_2_2_1","unstructured":"2008. CassandraDB. Retrieved October 14 2023 from https:\/\/github.com\/apache\/cassandra"},{"key":"e_1_2_2_3_1","unstructured":"2011. C Reference. Retrieved October 14 2023 from https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/lower_bound"},{"key":"e_1_2_2_4_1","unstructured":"2011. LevelDB. Retrieved October 14 2023 from https:\/\/github.com\/google\/leveldb"},{"key":"e_1_2_2_5_1","unstructured":"2012. RocksDB. Retrieved October 14 2023 from https:\/\/github.com\/facebook\/rocksdb"},{"key":"e_1_2_2_6_1","unstructured":"2019. PGM-Index. Retrieved October 14 2023 from https:\/\/github.com\/gvinciguerra\/PGM-index"},{"key":"e_1_2_2_7_1","volume-title":"Lyric Doshi, Tim Kraska, Xiaozhou, Li, Andy Ly, and Christopher Olston.","author":"Abu-Libdeh Hussam","year":"2020","unstructured":"Hussam Abu-Libdeh, Deniz Altinb\u00fcken, Alex Beutel, Ed H. Chi, Lyric Doshi, Tim Kraska, Xiaozhou, Li, Andy Ly, and Christopher Olston. 2020. Learned Indexes for a Google-scale Disk-based Database. http:\/\/arxiv.org\/abs\/2012.12501 arXiv:2012.12501 [cs]."},{"key":"e_1_2_2_8_1","unstructured":"Andrew Crotty. 2021. Hist-Tree: Those Who Ignore It Are Doomed to Learn.. In CIDR."},{"key":"e_1_2_2_9_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","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 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 155--171."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_2_12_1","volume-title":"International Conference on Machine Learning. PMLR, 3123--3132","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. 2020. Why are learned indexes so effective?. In International Conference on Machine Learning. PMLR, 3123--3132."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.04.015"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00031"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140402.1140409"},{"key":"e_1_2_2_18_1","volume-title":"SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2019. SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems (2019)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476392"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_22_1","unstructured":"Ani Kristo and Tim Kraska. 2023. Parallel External Sorting of ASCII Records Using Learned Models. http:\/\/arxiv.org\/ abs\/2305.05671 arXiv:2305.05671 [cs]."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389752"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589284"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_2_27_1","volume-title":"21st USENIX Conference on File and Storage Technologies (FAST 23)","author":"Li Pengfei","year":"2023","unstructured":"Pengfei Li, Yu Hua, Pengfei Zuo, Zhangyu Chen, and Jiajie Sheng. 2023. {ROLEX}: A Scalable {RDMA-oriented} Learned {Key-Value} Store for Disaggregated Memory Systems. In 21st USENIX Conference on File and Storage Technologies (FAST 23). 99--114."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_2_29_1","unstructured":"Yaliang Li Daoyuan Chen Bolin Ding Kai Zeng and Jingren Zhou. 2021. A Pluggable Learned Index Method via Sampling and Gap Insertion. http:\/\/arxiv.org\/abs\/2101.00808 arXiv:2101.00808 [cs]."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494141"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3118599"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570704"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510405"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384706"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464509"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--70504--8_12"},{"key":"e_1_2_2_39_1","unstructured":"Mihail Stoian Andreas Kipf Ryan Marcus and Tim Kraska. 2021. Towards Practical Learned Indexing. http: \/\/arxiv.org\/abs\/2108.05117 arXiv:2108.05117 [cs]."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575744"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594528"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468520"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551848"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2945947"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0355-0"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3561261.3561270"},{"key":"e_1_2_2_49_1","volume-title":"International Conference on Machine Learning. PMLR, 40669--40680","author":"Zeighami Sepanta","year":"2023","unstructured":"Sepanta Zeighami and Cyrus Shahabi. 2023. On distribution dependent sub-logarithmic query time of learned indexing. In International Conference on Machine Learning. PMLR, 40669--40680."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654919","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:42:51Z","timestamp":1755787371000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654919"],"URL":"https:\/\/doi.org\/10.1145\/3654919","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}