{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:22:24Z","timestamp":1783437744703,"version":"3.54.6"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>Index structures in memory systems become important to improve the entire system performance. The promising learned indexes leverage deep-learning models to complement existing index structures and obtain significant performance improvements. Existing schemes rely on a delta-buffer to support the scalability, which however incurs high overheads when a large number of data are inserted, due to the needs of checking both learned indexes and extra delta-buffer. The practical system performance also decreases since the shared delta-buffer quickly becomes large and requires frequent retraining due to high data dependency. To address the problems of limited scalability and frequent retraining, we propose a FINE-grained learned index scheme with high scalability, called FINEdex, which constructs independent models with a flattened data structure (i.e., the data arrays with low data dependency) under the trained data array to concurrently process the requests with low overheads. By further efficiently exploring and exploiting the characteristics of the workloads, FINEdex processes the new requests in-place with the support of non-blocking retraining, hence adapting to the new distributions without blocking the systems. We evaluate FINEdex via YCSB and real-world datasets, and extensive experimental results demonstrate that FINEdex improves the performance respectively by up to 1.8\u00d7 and 2.5\u00d7 than state-of-the-art XIndex and Masstree. We have released the open-source codes of FINEdex for public use in GitHub.<\/jats:p>","DOI":"10.14778\/3489496.3489512","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:28:36Z","timestamp":1644020916000},"page":"321-334","source":"Crossref","is-referenced-by-count":87,"title":["FINEdex"],"prefix":"10.14778","volume":"15","author":[{"given":"Pengfei","family":"Li","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Hua","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jingnan","family":"Jia","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pengfei","family":"Zuo","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. Symas lightning memory-mapped database. http:\/\/www.lmdb.tech\/doc\/  2017. Symas lightning memory-mapped database. http:\/\/www.lmdb.tech\/doc\/"},{"key":"e_1_2_1_2_1","unstructured":"2020. Intel AVX2. https:\/\/www.intel.com\/content\/www\/us\/en\/homepage.html  2020. Intel AVX2. https:\/\/www.intel.com\/content\/www\/us\/en\/homepage.html"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733094"},{"key":"e_1_2_1_4_1","unstructured":"Timo Bingmann. 2007. Stx b+tree c++ template classes. http:\/\/panthema.net\/2007\/stx-btree\/  Timo Bingmann. 2007. Stx b+tree c++ template classes. http:\/\/panthema.net\/2007\/stx-btree\/"},{"key":"e_1_2_1_5_1","first-page":"227","article-title":"Efficient in-memory indexing with generalized prefix trees. Database systems for Business","volume":"180","author":"Boehm Matthias","year":"2011","unstructured":"Matthias Boehm , Benjamin Schlegel , Peter Benjamin Volk , Ulrike Fischer , Dirk Habich , and Wolfgang Lehner . 2011 . Efficient in-memory indexing with generalized prefix trees. Database systems for Business , Technology and Web (BTW) 180 (2011), 227 -- 246 . Matthias Boehm, Benjamin Schlegel, Peter Benjamin Volk, Ulrike Fischer, Dirk Habich, and Wolfgang Lehner. 2011. Efficient in-memory indexing with generalized prefix trees. Database systems for Business, Technology and Web (BTW) 180 (2011), 227--246.","journal-title":"Technology and Web (BTW)"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463713"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368961"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386712"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672375"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277451"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_24"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386714"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325903"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407850"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488775"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.44"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482662"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_25_1","unstructured":"Sanjay Ghemawat and Jeff Dean. 2011. LevelDB. https:\/\/github.com\/google\/leveldb  Sanjay Ghemawat and Jeff Dean. 2011. LevelDB. https:\/\/github.com\/google\/leveldb"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.656226"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656370"},{"key":"e_1_2_1_28_1","unstructured":"The PostgreSQL Global Development Group. 1996--2021. PostgreSQL. https:\/\/www.postgresql.org\/  The PostgreSQL Global Development Group. 1996--2021. PostgreSQL. https:\/\/www.postgresql.org\/"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.33.2.25"},{"key":"e_1_2_1_31_1","unstructured":"IBM Inc. 2020. IBM DB2. https:\/\/www.ibm.com\/analytics\/db2  IBM Inc. 2020. IBM DB2. https:\/\/www.ibm.com\/analytics\/db2"},{"key":"e_1_2_1_32_1","unstructured":"MongoDB Inc. 2021. MongoDB. https:\/\/www.mongodb.com\/  MongoDB Inc. 2021. MongoDB. https:\/\/www.mongodb.com\/"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33615-7_27"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_35_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). 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_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3358807.3358870"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"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.5555\/1557465"},{"key":"e_1_2_1_44_1","volume-title":"Martin Farach-Colton and Yang Zhan","author":"Rob Johnson William Jannen","year":"2015","unstructured":"William Jannen Rob Johnson Bradley C Kuszmaul Donald E Porter Jun Yuan Michael A Bender , Martin Farach-Colton and Yang Zhan . 2015 . And introduction to Be-trees and write-optimization. Login; Magazine 40, 5 (2015). William Jannen Rob Johnson Bradley C Kuszmaul Donald E Porter Jun Yuan Michael A Bender, Martin Farach-Colton and Yang Zhan. 2015. And introduction to Be-trees and write-optimization. Login; Magazine 40, 5 (2015)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358758"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671362"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_48_1","unstructured":"redislabs. 2021. Redis. https:\/\/redis.io\/  redislabs. 2021. Redis. https:\/\/redis.io\/"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/3291168.3291193"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882918"},{"key":"e_1_2_1_51_1","volume-title":"International Conference on Learning Representations 2017 (ICLR).","author":"Shazeer Noam","year":"2017","unstructured":"Noam Shazeer , Azalia Mirhoseini , Krzysztof Maziarz , Andy Davis , Quoc Le , Geoffrey Hinton , and Jeff Dean . 2017 . Outrageously large neural networks: The sparsely-gated mixture-of-experts layer . In International Conference on Learning Representations 2017 (ICLR). Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. 2017. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In International Conference on Learning Representations 2017 (ICLR)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/3358807.3358836"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488773"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compind.2018.12.010"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303955"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0355-0"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3489496.3489512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:15:45Z","timestamp":1672226145000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3489496.3489512"}},"subtitle":["a fine-grained learned index scheme for scalable and concurrent memory systems"],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.14778\/3489496.3489512"],"URL":"https:\/\/doi.org\/10.14778\/3489496.3489512","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,10]]}}}