{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:49Z","timestamp":1750309489949,"version":"3.41.0"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T00:00:00Z","timestamp":1738972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"Ministry of Science and ICT (MSIT), Korea, under the Information Technology Research Center support program","award":["IITP-2024-2021-0-01817"],"award-info":[{"award-number":["IITP-2024-2021-0-01817"]}]},{"name":"Institute for Information & Communications Technology Planning & Evaluation (IITP), the National Research Foundation of Korea","award":["NRF-2023R1A2C2006432"],"award-info":[{"award-number":["NRF-2023R1A2C2006432"]}]},{"name":"Korea government","award":["RS-2024-00438729"],"award-info":[{"award-number":["RS-2024-00438729"]}]},{"name":"Development of Full Lifecycle Privacy-Preserving Techniques using Anonymized Confidential Computing","award":["RS-2024-00459026"],"award-info":[{"award-number":["RS-2024-00459026"]}]},{"name":"Energy-Aware Operating System for Disaggregated System), an NSF","award":["2312785"],"award-info":[{"award-number":["2312785"]}]},{"DOI":"10.13039\/100004358","name":"Samsung Electronics Co., Ltd","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004358","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2025,5,31]]},"abstract":"<jats:p>Many datasets in real life are complex and dynamic, that is, their key densities are varied over the whole key space and their key distributions change over time. It is challenging for an index structure to efficiently support all key operations for data management, in particular, search, insert, and scan, for such dynamic datasets. In this article, we present DyTIS (Dynamic dataset Targeted Index Structure), an index that targets dynamic datasets. DyTIS, although based on the structure of Extendible hashing, leverages the CDF of the key distribution of a dataset, and learns and adjusts its structure as the dataset grows. The key novelty behind DyTIS is to group keys by the natural key order and maintain keys in sorted order in each bucket to support scan operations within a hash index. We also define what we refer to as a dynamic dataset and propose a means to quantify its dynamic characteristics. Our experimental results show that DyTIS provides higher performance than the state-of-the-art learned index for the dynamic datasets considered. We also analyze the effects of the dynamic characteristics of datasets, including sequential datasets, as well as the effect of multiple threads on the performance of the indexes.<\/jats:p>","DOI":"10.1145\/3707642","type":"journal-article","created":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T10:51:27Z","timestamp":1734519087000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Dynamic Characteristic Aware Index Structure Optimized for Real-world Datasets"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5348-7808","authenticated-orcid":false,"given":"Jin","family":"Yang","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, UNIST, Ulsan, Korea (the Republic of)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5983-1016","authenticated-orcid":false,"given":"Heejin","family":"Yoon","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, UNIST, Ulsan, Korea (the Republic of)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8725-1534","authenticated-orcid":false,"given":"Gyeongchan","family":"Yun","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, UNIST, Ulsan, Korea (the Republic of)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9152-0321","authenticated-orcid":false,"given":"Sam H.","family":"Noh","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Virginia Tech, Blacksburg, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4391-4470","authenticated-orcid":false,"given":"Young-Ri","family":"Choi","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, UNIST, Ulsan, Korea (the Republic of)"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,8]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Memcached. 2004. Memcached Home Page. Retrieved December 20 2024 from http:\/\/memcached.org\/"},{"key":"e_1_3_2_3_2","unstructured":"GitHub. 2007. STX B+-tree. Retrieved December 20 2024 from https:\/\/github.com\/bingmann\/stx-btree"},{"key":"e_1_3_2_4_2","unstructured":"Redis. 2009. Redis Home Page. Retrieved December 20 2024 from https:\/\/redis.io\/docs\/management\/scaling\/"},{"key":"e_1_3_2_5_2","unstructured":"2011. Kyoto Cabinet: A Straightforward Implementation of DBM. Retrieved December 20 2024 from https:\/\/dbmx.net\/kyotocabinet\/"},{"key":"e_1_3_2_6_2","unstructured":"Fallabs Tech. 2014. A Fast and Lightweight Key-Value Store Library by Google. Retrieved December 20 2024 from http:\/\/code.google.com\/p\/leveldb"},{"key":"e_1_3_2_7_2","unstructured":"H-Store. 2016. H-Store Home Page. Retrieved December 20 2024 from https:\/\/hstore.cs.brown.edu\/"},{"key":"e_1_3_2_8_2","unstructured":"GitHub. 2020. ALEX. Retrieved December 20 2024 from https:\/\/github.com\/microsoft\/ALEX\/tree\/57efb5"},{"key":"e_1_3_2_9_2","unstructured":"XIndex. 2020. XIndex: Project Information. Retrieved December 20 2024 from https:\/\/ipads.se.sjtu.edu.cn:1312\/opensource\/xindex"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.is.2015.04.007","article-title":"Time-series clustering\u2014A decade review","author":"Aghabozorgi Saeed","year":"2015","unstructured":"Saeed Aghabozorgi, Ali Seyed Shirkhorshidi, and Teh Ying Wah. 2015. Time-series clustering\u2014A decade review. Information Systems 53 (2015), 16\u201338.","journal-title":"Information Systems"},{"key":"e_1_3_2_11_2","volume-title":"Proceedings of the 5th International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM \u201922)","author":"Andersen Mikkel M\u00f8ller","year":"2022","unstructured":"Mikkel M\u00f8ller Andersen and Pinar T\u00f6z\u00fcn. 2022. Micro-architectural analysis of a learned index. In Proceedings of the 5th International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM \u201922). Article 5, 12 pages."},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/978-1-4612-5098-2_12","article-title":"Monthly mean sunspot numbers","author":"Andrews D. F.","year":"1985","unstructured":"D. F. Andrews, A. M. Herzberg, D. F. Andrews, and A. M. Herzberg. 1985. Monthly mean sunspot numbers. In Data: A Collection of Problems from Many Fields for the Student and Research Worker. Springer Series in Statistics. Springer, 67\u201374.","journal-title":"Data: A Collection of Problems from Many Fields for the Student and Research Worker."},{"key":"e_1_3_2_13_2","unstructured":"Timo Bingmann. 2007. STX B+ Tree C++ Template Classes. Retrieved December 20 2024 from https:\/\/panthema.net\/2007\/stx-btree\/"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386712"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2505464"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672375"},{"key":"e_1_3_2_17_2","first-page":"799","volume-title":"Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC \u201920)","author":"Chen Zhangyu","year":"2020","unstructured":"Zhangyu Chen, Yu Huang, Bo Ding, and Pengfei Zuo. 2020. Lock-free concurrent level hashing for persistent memory. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC \u201920). 799\u2013812."},{"key":"e_1_3_2_18_2","article-title":"TLC Trip Record Data","author":"Commission NYC Taxi & Limousine","year":"2020","unstructured":"NYC Taxi & Limousine Commission. 2020. TLC Trip Record Data. Retrieved December 20, 2024 from https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page","journal-title":"https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/1807128.1807152","volume-title":"Proceedings of the ACM Symposium on Cloud Computing (SoCC \u201910)","author":"Cooper Brian F.","year":"2010","unstructured":"Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the ACM Symposium on Cloud Computing (SoCC \u201910). 143\u2013154."},{"key":"e_1_3_2_20_2","article-title":"Toshiba Memory Corporation Introduces XL-FLASH\u2122 Storage Class Memory Solution","author":"Corporation Toshiba Memory","year":"2019","unstructured":"Toshiba Memory Corporation. 2019. Toshiba Memory Corporation Introduces XL-FLASH\u2122 Storage Class Memory Solution. Retrieved December 20, 2024 from https:\/\/www.kioxia.com\/en-jp\/about\/news\/2019\/20190806-1.html","journal-title":"https:\/\/www.kioxia.com\/en-jp\/about\/news\/2019\/20190806-1.html"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3605573.3605590"},{"key":"e_1_3_2_22_2","first-page":"155","volume-title":"Proceedings of 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201920)","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 Proceedings of 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201920). 155\u2013171."},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1145\/2786763.2694359","article-title":"Asynchronized concurrency: The secret to scaling concurrent search data structures","author":"David Tudor","year":"2015","unstructured":"Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized concurrency: The secret to scaling concurrent search data structures. ACM SIGARCH Computer Architecture News 43, 1 (2015), 631\u2013644.","journal-title":"ACM SIGARCH Computer Architecture News"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_3_2_26_2","first-page":"14, 2 (2020), 7","volume-title":"Proceedings of the VLDB Endowment","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. Proceedings of the VLDB Endowment14, 2 (2020), 74\u201386."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/588058.588072"},{"key":"e_1_3_2_28_2","first-page":"Article 12, 34","article-title":"Time-series data mining","author":"Esling Philippe","year":"2012","unstructured":"Philippe Esling and Carlos Agon. 2012. Time-series data mining. ACM Computing Surveys 45, 1 (2012), Article 12, 34 pages.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_2_29_2","first-page":"1","article-title":"Main memory database systems","author":"Faerber Franz","year":"2017","unstructured":"Franz Faerber, Alfons Kemper, Per-\u00c5ke Larson, Justin Levandoski, Thomas Neumann, and Andrew Pavlo. 2017. Main memory database systems. Foundations and Trends\u00ae in Databases 8, 1-2 (2017), 1\u2013130.","journal-title":"Foundations and Trends\u00ae in Databases"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","article-title":"Extendible hashing\u2014A fast access method for dynamic files","author":"Fagin Ronald","year":"1979","unstructured":"Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, and H. Raymond Strong. 1979. Extendible hashing\u2014A fast access method for dynamic files. ACM Transactions on Database Systems 4, 3 (1979), 315\u2013344.","journal-title":"ACM Transactions on Database Systems"},{"key":"e_1_3_2_31_2","first-page":"13, 8 (2020), 1","volume-title":"Proceedings of the VLDB Endowment","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment13, 8 (2020), 1162\u20131175."},{"key":"e_1_3_2_32_2","first-page":"5","article-title":"Distributed caching with Memcached","author":"Fitzpatrick Brad","year":"2004","unstructured":"Brad Fitzpatrick. 2004. Distributed caching with Memcached. Linux Journal 2004 (2004), 5.","journal-title":"Linux Journal"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_3_2_34_2","first-page":"315","volume-title":"Proceedings of the 2023 IEEE 39th International Conference on Data Engineering (ICDE \u201923)","author":"Ge Jiake","year":"2023","unstructured":"Jiake Ge, Boyu Shi, Yanfeng Chai, Yuanhui Luo, Yunda Guo, Yinxuan He, and Yunpeng Chai. 2023. Cutting learned index into pieces: An in-depth inquiry into updatable learned indexes. In Proceedings of the 2023 IEEE 39th International Conference on Data Engineering (ICDE \u201923). 315\u2013327."},{"key":"e_1_3_2_35_2","article-title":"OpenStreetMap Data Extracts","year":"2019","unstructured":"Geofabrik. 2019. OpenStreetMap Data Extracts. Retrieved December 20, 2024 from https:\/\/download.geofabrik.de\/","journal-title":"https:\/\/download.geofabrik.de\/"},{"key":"e_1_3_2_36_2","volume-title":"Data Mining: Concepts and Techniques","author":"Han Jiawei","year":"2022","unstructured":"Jiawei Han, Jian Pei, and Hanghang Tong. 2022. Data Mining: Concepts and Techniques (4th ed.). The Morgan Kaufmann Series in Data Management Systems. Morgan Kaufmann."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2003.1203503"},{"key":"e_1_3_2_38_2","first-page":"187","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST \u201918)","author":"Hwang Deukyeon","year":"2018","unstructured":"Deukyeon Hwang, Wook-Hee Kim, Youjip Won, and Beomseok Nam. 2018. Endurable transient inconsistency in byte-addressable persistent B+-tree. In Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST \u201918). 187\u2013200."},{"key":"e_1_3_2_39_2","volume-title":"Intel VTune Profiler","author":"Corporation Intel","year":"2024","unstructured":"Intel Corporation. 2024. Intel VTune Profiler. Retrieved December 20, 2024 from https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/vtune-profiler.html"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/366532.366540","article-title":"An indirect chaining method for addressing on secondary keys","author":"Johnson L. R.","year":"1961","unstructured":"L. R. Johnson. 1961. An indirect chaining method for addressing on secondary keys. Communications of the ACM 4, 5 (1961), 218\u2013222.","journal-title":"Communications of the ACM"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3538643.3539745"},{"key":"e_1_3_2_42_2","first-page":"191","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST \u201919)","author":"Kaiyrakhmet Olzhas","year":"2019","unstructured":"Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H. Noh, and Young-ri Choi. 2019. SLM-DB: Single-level key-value store with persistent memory. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST \u201919). 191\u2013205."},{"key":"e_1_3_2_43_2","first-page":"1, 2 (2008), 14","volume-title":"Proceedings of the VLDB Endowment","author":"Kallman Robert","year":"2008","unstructured":"Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alexander Rasin, Stanley Zdonik, Evan P. C. Jones, Samuel Madden, Michael Stonebraker, Yang Zhang, et\u00a0al. 2008. H-Store: A high-performance, distributed main memory transaction processing system. Proceedings of the VLDB Endowment1, 2 (2008), 1496\u20131499."},{"key":"e_1_3_2_44_2","first-page":"57","volume-title":"Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC \u201916)","author":"Kejriwal Ankita","year":"2016","unstructured":"Ankita Kejriwal, Arjun Gopalan, Ashish Gupta, Zhihao Jia, Stephen Yang, and John Ousterhout. 2016. SLIK: Scalable low-latency indexes for a key-value store. In Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC \u201916). 57\u201370."},{"key":"e_1_3_2_45_2","first-page":"161","volume-title":"Proceedings of 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201922)","author":"Kim Wonbae","year":"2022","unstructured":"Wonbae Kim, Chanyeol Park, Dongui Kim, Hyeongjun Park, Young-ri Choi, Alan Sussman, and Beomseok Nam. 2022. ListDB: Union of write-ahead logs and persistent SkipLists for incremental checkpointing on persistent memory. In Proceedings of 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201922). 161\u2013177."},{"key":"e_1_3_2_46_2","volume-title":"Proceedings of the 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. In Proceedings of the NeurIPS Workshop on Machine Learning for Systems."},{"key":"e_1_3_2_47_2","first-page":"1","volume-title":"Proceedings of the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM \u201920)","author":"Kipf Andreas","year":"2020","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 Proceedings of the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM \u201920). 1\u20135."},{"key":"e_1_3_2_48_2","volume-title":"Proceedings of the 9th Biennial Conference on Innovative Data Systems Research (CIDR \u201919)","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 Proceedings of the 9th Biennial Conference on Innovative Data Systems Research (CIDR \u201919)."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_3_2_50_2","volume-title":"Information Theory and Statistics","author":"Kullback Solomon","year":"1997","unstructured":"Solomon Kullback. 1997. Information Theory and Statistics. Courier Corporation."},{"key":"e_1_3_2_51_2","first-page":"26","volume-title":"Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE \u201913)","author":"Levandoski Justin J.","year":"2013","unstructured":"Justin J. Levandoski, Per-\u00c5ke Larson, and Radu Stoica. 2013. Identifying hot and cold data in main-memory databases. In Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE \u201913). 26\u201337."},{"key":"e_1_3_2_52_2","first-page":"321","article-title":"FINEdex: A fine-grained learned index scheme for scalable and concurrent memory systems","author":"Li Pengfei","year":"2021","unstructured":"Pengfei Li, Yu Hua, Jingnan Jia, and Pengfei Zuo. 2021. FINEdex: A fine-grained learned index scheme for scalable and concurrent memory systems. Proceedings of the VLDB Endowment 15, 2 (2021), 321\u2013334.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_53_2","first-page":"15, 3 (2021), 5","volume-title":"Proceedings of the VLDB Endowment","author":"Lu Baotong","year":"2021","unstructured":"Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang. 2021. APEX: A high-performance learned index on persistent memory. Proceedings of the VLDB Endowment15, 3 (2021), 597\u2013610."},{"key":"e_1_3_2_54_2","first-page":"561","article-title":"FILM: A fully learned index for larger-than-memory databases","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. Proceedings of the VLDB Endowment 16, 3 (2022), 561\u2013573.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_2_56_2","first-page":"14, 1 (2020), 1","volume-title":"Proceedings of the VLDB Endowment","author":"Marcus Ryan","year":"2020","unstructured":"Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. 2020. Benchmarking learned indexes. Proceedings of the VLDB Endowment14, 1 (2020), 1\u201313."},{"key":"e_1_3_2_57_2","first-page":"14, 1 (2020), 1","volume-title":"Proceedings of the VLDB Endowment","author":"Marcus Ryan","year":"2020","unstructured":"Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. 2020. Benchmarking learned indexes. Proceedings of the VLDB Endowment14, 1 (2020), 1\u201313."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883044"},{"key":"e_1_3_2_59_2","first-page":"175","volume-title":"AUUG Conference Proceedings","author":"McKenney Paul E.","year":"2001","unstructured":"Paul E. McKenney, Jonathan Appavoo, Andi Kleen, Orran Krieger, Rusty Russell, Dipankar Sarma, and Maneesh Soni. 2001. Read-copy update. In AUUG Conference Proceedings. AUUG, 175."},{"key":"e_1_3_2_60_2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/362851.362882","article-title":"Scatter storage techniques","author":"Morris Robert","year":"1968","unstructured":"Robert Morris. 1968. Scatter storage techniques. Communications of the ACM 11, 1 (1968), 38\u201344.","journal-title":"Communications of the ACM"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323302"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_3_2_63_2","first-page":"627","volume-title":"Proceedings of the 2014 IEEE 34th the International Conference on Distributed Computing Systems (ICDCS \u201914)","author":"Nguyen N.","year":"2014","unstructured":"N. Nguyen and P. Tsigas. 2014. Lock-free cuckoo hashing. In Proceedings of the 2014 IEEE 34th the International Conference on Distributed Computing Systems (ICDCS \u201914). 627\u2013636."},{"key":"e_1_3_2_64_2","article-title":"Amazon AWS","author":"AWS OpenStreetMap on","year":"2021","unstructured":"OpenStreetMap on AWS. 2021. Amazon AWS. Retrieved December 20, 2024 from https:\/\/registry.opendata.aws\/osm\/","journal-title":"https:\/\/registry.opendata.aws\/osm\/"},{"key":"e_1_3_2_65_2","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","article-title":"Cuckoo hashing","author":"Pagh Rasmus","year":"2004","unstructured":"Rasmus Pagh and Flemming Friche Rodler. 2004. Cuckoo hashing. Journal of Algorithms 51, 2 (2004), 122\u2013144.","journal-title":"Journal of Algorithms"},{"key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","article-title":"Addressing for random-access storage","author":"Peterson W. W.","year":"1957","unstructured":"W. W. Peterson. 1957. Addressing for random-access storage. IBM Journal of Research and Development 1, 2 (1957), 130\u2013146.","journal-title":"IBM Journal of Research and Development"},{"key":"e_1_3_2_67_2","unstructured":"Samsung. 2017. Ultra-Low Latency with Samsung Z-NAND SSD. Retrieved December 20 2024 from https:\/\/download.semiconductor.samsung.com\/resources\/brochure\/Ultra-Low%20Latency%20with%20Samsung%20Z-NAND%20SSD.pdf"},{"key":"e_1_3_2_68_2","first-page":"1","volume-title":"Proceedings of 3rd International Workshop on Applied AI for Database Systems and Applications (AIDB \u201921)","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. In Proceedings of 3rd International Workshop on Applied AI for Database Systems and Applications (AIDB \u201921). 1\u20135."},{"key":"e_1_3_2_69_2","first-page":"21","article-title":"The VoltDB main memory DBMS.","author":"Stonebraker Michael","year":"2013","unstructured":"Michael Stonebraker and Ariel Weisberg. 2013. The VoltDB main memory DBMS. IEEE Database Engineering Bulletin 2013 (2013), 21\u201327.","journal-title":"IEEE Database Engineering Bulletin"},{"key":"e_1_3_2_70_2","first-page":"1992","article-title":"Learned index: A comprehensive experimental evaluation","author":"Sun Zhaoyan","year":"2023","unstructured":"Zhaoyan Sun, Xuanhe Zhou, and Guoliang Li. 2023. Learned index: A comprehensive experimental evaluation. Proceedings of the VLDB Endowment 16, 8 (2023), 1992\u20132004.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.5555\/2002181.2002192"},{"key":"e_1_3_2_73_2","first-page":"93","volume-title":"Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201921)","author":"Wang Qing","year":"2021","unstructured":"Qing Wang, Youyou Lu, Junru Li, and Jiwu Shu. 2021. Nap: A black-box approach to NUMA-Aware persistent memory indexes. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201921). 93\u2013111."},{"key":"e_1_3_2_74_2","first-page":"461","volume-title":"Proceedings of the 2018 IEEE 34th International Conference on Data Engineering (ICDE \u201918)","author":"Wang Tianzheng","year":"2018","unstructured":"Tianzheng Wang, Justin Levandoski, and Per-Ake Larson. 2018. Easy lock-free indexing in non-volatile memory. In Proceedings of the 2018 IEEE 34th International Conference on Data Engineering (ICDE \u201918). 461\u2013472."},{"key":"e_1_3_2_75_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3409963.3410496","volume-title":"Proceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems (APSys \u201920)","author":"Wang Youyun","year":"2020","unstructured":"Youyun Wang, Chuzhe Tang, Zhaoguo Wang, and Haibo Chen. 2020. SIndex: A scalable learned index for string keys. In Proceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems (APSys \u201920). 17\u201324."},{"key":"e_1_3_2_76_2","first-page":"15, 11 (2022),","volume-title":"Proceedings of the VLDB Endowment","author":"Wongkham Chaichon","year":"2022","unstructured":"Chaichon Wongkham, Baotong Lu, Chris Liu, Zhicong Zhong, Eric Lo, and Tianzheng Wang. 2022. Are updatable learned indexes ready? Proceedings of the VLDB Endowment15, 11 (2022), 3004\u20133017."},{"key":"e_1_3_2_77_2","first-page":"14, 8 (2021), 1","volume-title":"Proceedings of the VLDB Endowment","author":"Wu Jiacheng","year":"2021","unstructured":"Jiacheng Wu, Yong Zhang, Shimin Chen, Yu Chen, Jin Wang, and Chunxiao Xing. 2021. Updatable learned index with precise positions. Proceedings of the VLDB Endowment14, 8 (2021), 1276\u20131288."},{"key":"e_1_3_2_78_2","article-title":"NFL: Robust learned index via distribution transformation","author":"Wu Shangyu","year":"2022","unstructured":"Shangyu Wu, Yufei Cui, Jinghuan Yu, Xuan Sun, Tei-Wei Kuo, and Chun Jason Xue. 2022. NFL: Robust learned index via distribution transformation. arXiv preprint arXiv:2205.11807 (2022).","journal-title":"arXiv preprint arXiv:2205.11807"},{"key":"e_1_3_2_79_2","first-page":"1","volume-title":"Proceedings of the 14th ACM European Conference on Computer Systems (EuroSys \u201919)","author":"Wu Xingbo","year":"2019","unstructured":"Xingbo Wu, Fan Ni, and Song Jiang. 2019. Wormhole: A fast ordered index for in-memory data management. In Proceedings of the 14th ACM European Conference on Computer Systems (EuroSys \u201919). 1\u201316."},{"key":"e_1_3_2_80_2","first-page":"349","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC \u201917)","author":"Xia Fei","year":"2017","unstructured":"Fei Xia, Dejun Jiang, Jin Xiong, and Ninghui Sun. 2017. HiKV: A hybrid index key-value store for DRAM-NVM memory systems. In Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC \u201917). 349\u2013362."},{"key":"e_1_3_2_81_2","doi-asserted-by":"crossref","unstructured":"Qing Xie Chaoyi Pang Xiaofang Zhou Xiangliang Zhang and Ke Deng. 2014. Maximum error-bounded piecewise linear representation for online stream approximation. VLDB Journal 23 (2014) 915\u2013937.","DOI":"10.1007\/s00778-014-0355-0"},{"key":"e_1_3_2_82_2","first-page":"800","volume-title":"Proceedings of the 18th European Conference on Computer Systems (EuroSys \u201923)","author":"Yang Jin","year":"2023","unstructured":"Jin Yang, Heejin Yoon, Gyeongchan Yun, Sam H. Noh, and Young-ri Choi. 2023. DyTIS: A dynamic dataset targeted index structure simultaneously efficient for search, insert, and scan. In Proceedings of the 18th European Conference on Computer Systems (EuroSys \u201923). 800\u2013816."},{"key":"e_1_3_2_83_2","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/3477132.3483551","volume-title":"Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP \u201921)","author":"Zeitak Adar","year":"2021","unstructured":"Adar Zeitak and Adam Morrison. 2021. Cuckoo Trie: Exploiting memory-level parallelism for efficient DRAM indexing. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP \u201921). 147\u2013162."},{"key":"e_1_3_2_84_2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.14778\/3565816.3565826","article-title":"PLIN: A persistent learned index for non-volatile memory with high performance and instant recovery","author":"Zhang Zhou","year":"2022","unstructured":"Zhou Zhang, Zhaole Chu, Peiquan Jin, Yongping Luo, Xike Xie, Shouhong Wan, Yun Luo, Xufei Wu, Peng Zou, Chunyang Zheng, et al.2022. PLIN: A persistent learned index for non-volatile memory with high performance and instant recovery. Proceedings of the VLDB Endowment 16, 2 (2022), 243\u2013255.","journal-title":"Proceedings of the VLDB Endowment"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3707642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:38Z","timestamp":1750295858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,8]]},"references-count":83,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,31]]}},"alternative-id":["10.1145\/3707642"],"URL":"https:\/\/doi.org\/10.1145\/3707642","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2025,2,8]]},"assertion":[{"value":"2024-04-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}