{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T06:48:16Z","timestamp":1775890096784,"version":"3.50.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:p>Learned indexes use machine learning models to learn the mappings between keys and their corresponding positions in key-value indexes. These indexes use the mapping information as training data. Learned indexes require frequent retrainings of their models to incorporate the changes introduced by update queries. To efficiently retrain the models, existing learned index systems often harness a linear algebraic QR factorization technique that performs matrix decomposition. This factorization approach processes all key-position pairs during each retraining, resulting in compute operations that grow linearly with the total number of keys and their lengths. Consequently, the retrainings create a severe performance bottleneck, especially for variable-length string keys, while the retrainings are crucial for maintaining high prediction accuracy and in turn, ensuring low query service latency.<\/jats:p>\n          <jats:p>To address this performance problem, we develop an algorithm-hardware co-designed string-key learned index system, dubbed SIA. In designing SIA, we leverage a unique algorithmic property of the matrix decomposition-based training method. Exploiting the property, we develop a memoization-based incremental training scheme, which only requires computation over updated keys, while decomposition results of non-updated keys from previous computations can be reused. We further enhance SIA to offload a portion of this training process to an FPGA accelerator to not only relieve CPU resources for serving index queries (i.e., inference), but also accelerate the training itself. Our evaluation shows that compared to ALEX, LIPP, and SIndex, a state-of-the-art learned index systems, SIA-accelerated learned indexes offer 2.6\u00d7 and 3.4\u00d7 higher throughput on the two real-world benchmark suites, YCSB and Twitter cache trace, respectively.<\/jats:p>","DOI":"10.14778\/3659437.3659439","type":"journal-article","created":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T16:22:27Z","timestamp":1717172547000},"page":"1802-1815","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Accelerating String-Key Learned Index Structures via Memoization-Based Incremental Training"],"prefix":"10.14778","volume":"17","author":[{"given":"Minsu","family":"Kim","sequence":"first","affiliation":[{"name":"KAIST"}]},{"given":"Jinwoo","family":"Hwang","sequence":"additional","affiliation":[{"name":"KAIST"}]},{"given":"Guseul","family":"Heo","sequence":"additional","affiliation":[{"name":"KAIST"}]},{"given":"Seiyeon","family":"Cho","sequence":"additional","affiliation":[{"name":"KAIST"}]},{"given":"Divya","family":"Mahajan","sequence":"additional","affiliation":[{"name":"Georgia Tech"}]},{"given":"Jongse","family":"Park","sequence":"additional","affiliation":[{"name":"KAIST"}]}],"member":"320","published-online":{"date-parts":[[2024,5,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Lyric Pankaj Doshi, Tim Klas Kraska, Xiaozhou (Steve) Li, Andy Ly, and Chris Olston (Eds.).","author":"Abu-Libdeh Hussam","year":"2020","unstructured":"Hussam Abu-Libdeh, Deniz Alt\u0131nb\u00fcken, Alex Beutel, Ed H. Chi, Lyric Pankaj Doshi, Tim Klas Kraska, Xiaozhou (Steve) Li, Andy Ly, and Chris Olston (Eds.). 2020. Learned Indexes for a Google-scale Disk-based Database. https:\/\/arxiv.org\/pdf\/2012.12501.pdf"},{"key":"e_1_2_1_2_1","unstructured":"ADpower. 2023. Wattman (HPM-100A). http:\/\/adpower21com.cafe24.com\/shop2\/product\/wattman-hpm-100a\/17."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2435779"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533702.3534917"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3492321.3519592"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447775"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3327144.3327258"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_9_1","volume-title":"Conference on Innovative Data Systems Research (CIDR'21)","author":"Crotty Andrew","year":"2021","unstructured":"Andrew Crotty. 2021. Hist-Tree: Those Who Ignore It Are Doomed to Learn. In Conference on Innovative Data Systems Research (CIDR'21)."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20)","author":"Dai Yifan","unstructured":"Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2020. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20). USENIX Association, USA, Article 9, 17 pages."},{"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\/3425879.3425880"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/qjmam\/1.1.149"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1032002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3603581.3603598"},{"key":"e_1_2_1_18_1","volume-title":"Van Loan","author":"Golub Gene H.","year":"1996","unstructured":"Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations (third ed.). The Johns Hopkins University Press."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471500"},{"key":"e_1_2_1_20_1","unstructured":"Milad Hashemi Kevin Swersky Jamie A. Smith Grant Ayers Heiner Litz Jichuan Chang Christos Kozyrakis and Parthasarathy Ranganathan. 2018. Learning Memory Access Patterns. arXiv:1803.02329 http:\/\/arxiv.org\/abs\/1803.02329"},{"key":"e_1_2_1_21_1","first-page":"902","article-title":"Burst Tries: A Fast, Efficient Data Structure for String Keys","volume":"20","author":"Heinz Steffen","year":"2002","unstructured":"Steffen Heinz, Justin Zobel, and Hugh E. Williams. 2002. Burst Tries: A Fast, Efficient Data Structure for String Keys. ACM Transactions on Information Systems 20, 2 (2002), 902--915.","journal-title":"ACM Transactions on Information Systems"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1020096"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/320941.320947"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC'20). USENIX Association, USA, Article 12","author":"Im Junsu","year":"2020","unstructured":"Junsu Im, Jinwook Bae, Chanwoo Chung, Arvind Arvind, and Sungjin Lee. 2020. PinK: High-Speed in-Storage Key-Value Store with Bounded Tails. In Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC'20). USENIX Association, USA, Article 12, 15 pages."},{"key":"e_1_2_1_25_1","unstructured":"Intel. 2023. Intel FPGA. https:\/\/www.intel.com\/content\/www\/us\/en\/products\/details\/fpga.html."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554828"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589284"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3174243.3174273"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359635"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557077"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"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.14778\/3598581.3598593"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494141"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570704"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236188"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2016.7446050"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384706"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1018"},{"key":"e_1_2_1_45_1","unstructured":"Nvidia. 2023. Nvidia Flex NIC with FPGA. https:\/\/www.nvidia.com\/en-us\/networking\/ethernet\/innova-2-flex\/."},{"key":"e_1_2_1_46_1","volume-title":"Scale-Out Acceleration for Machine Learning. In 2017 50th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 367--381","author":"Park Jongse","year":"2017","unstructured":"Jongse Park, Hardik Sharma, Divya Mahajan, Joon Kyung Kim, Preston Olds, and Hadi Esmaeilzadeh. 2017. Scale-Out Acceleration for Machine Learning. In 2017 50th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO). 367--381."},{"key":"e_1_2_1_47_1","volume-title":"Parallel Block Schemes for Large-Scale Least-Squares Computations","author":"Plemmons Robert J","unstructured":"Robert J Plemmons. 1988. Parallel Block Schemes for Large-Scale Least-Squares Computations. Urbana: University of Illinois Press."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2015.42"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2012.6339142"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783720"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589332"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565848"},{"key":"e_1_2_1_53_1","volume-title":"Umar Farooq Minhas, and Tim Kraska","author":"Spector Benjamin","year":"2021","unstructured":"Benjamin Spector, Andreas Kipf, Kapil Vaidya, Chi Wang, Umar Farooq Minhas, and Tim Kraska. 2021. Bounding the Last Mile: Efficient Learned String Indexing. arXiv:2111.14905 [cs.DB]"},{"key":"e_1_2_1_54_1","unstructured":"Mihail Stoian Andreas Kipf Ryan Marcus and Tim Kraska. 2021. Towards Practical Learned Indexing. arXiv:2108.05117 [cs.DB]"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575744"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594528"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611520"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Shengzhe Wang Zihang Lin Suzhen Wu Hong Jiang Jie Zhang and Bo Mao. 2023. LearnedFTL: A Learning-based Page-level FTL for Improving Random Reads in Flash-based SSDs. arXiv:2303.13226 [cs.AR]","DOI":"10.1109\/HPCA57654.2024.00054"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565819"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409963.3410496"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2817118"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468520"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547322"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303955"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472883.3487012"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3552326.3587434"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20)","author":"Yang Juncheng","unstructured":"Juncheng Yang, Yao Yue, and K. V. Rashmi. 2020. A Large Scale Analysis of Hundreds of In-Memory Cache Clusters at Twitter. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20). USENIX Association, USA, Article 11, 18 pages."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.14778\/3561261.3561270"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483551"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551823"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470892"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565826"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-021-1348-2"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-95391-1_46"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3659437.3659439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T16:28:32Z","timestamp":1717172912000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3659437.3659439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4]]},"references-count":76,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.14778\/3659437.3659439"],"URL":"https:\/\/doi.org\/10.14778\/3659437.3659439","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,4]]},"assertion":[{"value":"2024-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}