{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T22:30:50Z","timestamp":1784154650072,"version":"3.55.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p>Non-Volatile Memory (NVM) has emerged as an alternative to next-generation main memories. Although many tree indices have been proposed for NVM, they generally use B+-tree-like structures. To further improve the performance of NVM-aware indices, we consider integrating learned indexes into NVM. The challenges of such an integration are two fold: (1) existing NVM indices rely on small nodes to accelerate insertions with crash consistency, but learned indices use huge nodes to obtain a flat structure. (2) the node structure of learned indices is not NVM friendly, meaning that accessing a learned node will cause multiple NVM block misses. Thus, in this paper, we propose a new persistent learned index called PLIN. The novelty of PLIN lies in four aspects: an NVM-aware data placement strategy, locally unordered and globally ordered leaf nodes, a model copy mechanism, and a hierarchical insertion strategy. In addition, PLIN is proposed for the NVM-only architecture, which can support instant recovery. We also present optimistic concurrency control and fine-grained locking mechanisms to make PLIN scalable to concurrent requests. We conduct experiments on real persistent memory with various workloads and compare PLIN with APEX, PACtree, ROART, TLBtree, and Fast&amp;Fair. The results show that PLIN achieves 2.08x higher insertion performance and 4.42x higher query performance than its competitors on average. Meanwhile, PLIN only needs ~30 \u03bcs to recover from a system crash.<\/jats:p>","DOI":"10.14778\/3565816.3565826","type":"journal-article","created":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:35:16Z","timestamp":1669250116000},"page":"243-255","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["PLIN"],"prefix":"10.14778","volume":"16","author":[{"given":"Zhou","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Science of Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhaole","family":"Chu","sequence":"additional","affiliation":[{"name":"University of Science of Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peiquan","family":"Jin","sequence":"additional","affiliation":[{"name":"University of Science of Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongping","family":"Luo","sequence":"additional","affiliation":[{"name":"University of Science of Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xike","family":"Xie","sequence":"additional","affiliation":[{"name":"University of Science of Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shouhong","family":"Wan","sequence":"additional","affiliation":[{"name":"University of Science of Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yun","family":"Luo","sequence":"additional","affiliation":[{"name":"Tencent"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xufei","family":"Wu","sequence":"additional","affiliation":[{"name":"Tencent"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peng","family":"Zou","sequence":"additional","affiliation":[{"name":"Tencent"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chunyang","family":"Zheng","sequence":"additional","affiliation":[{"name":"Intel Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guoan","family":"Wu","sequence":"additional","affiliation":[{"name":"Intel Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andy","family":"Rudoff","sequence":"additional","affiliation":[{"name":"Intel Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3164147"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292616"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394025"},{"key":"e_1_2_1_4_1","volume-title":"HardBD@ICDE","author":"Chen Leying","unstructured":"Leying Chen and Shimin Chen . 2021. How does updatable learned index perform on non-volatile main memory? . In HardBD@ICDE . IEEE Computer Society , Chania, Greece , 66--71. Leying Chen and Shimin Chen. 2021. How does updatable learned index perform on non-volatile main memory?. In HardBD@ICDE. IEEE Computer Society, Chania, Greece, 66--71."},{"key":"e_1_2_1_5_1","volume-title":"CIDR. www.cidrdb.org","author":"Chen Shimin","unstructured":"Shimin Chen , Phillip B. Gibbons , and Suman Nath . 2011. Rethinking database algorithms for phase change memory . In CIDR. www.cidrdb.org , Asilomar, CA, USA , 21--31. Shimin Chen, Phillip B. Gibbons, and Suman Nath. 2011. Rethinking database algorithms for phase change memory. In CIDR. www.cidrdb.org, Asilomar, CA, USA, 21--31."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407850"},{"key":"e_1_2_1_8_1","volume-title":"SoCC","author":"Cooper Brian F.","unstructured":"Brian F. Cooper , Adam Silberstein , Erwin Tam , Raghu Ramakrishnan , and Russell Sears . 2010. Benchmarking cloud serving systems with YCSB . In SoCC . ACM , Indianapolis, Indiana , 143--154. Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In SoCC. ACM, Indianapolis, Indiana, 143--154."},{"key":"e_1_2_1_9_1","volume-title":"Lawrence Benson, and Tilmann Rabl.","author":"Daase Bj\u00f6rn","year":"2021","unstructured":"Bj\u00f6rn Daase , Lars Jonas Bollmeier , Lawrence Benson, and Tilmann Rabl. 2021 . Maximizing persistent memory bandwidth utilization for OLAP workloads. In SIGMOD. ACM, Virtual Event, China , 339--351. Bj\u00f6rn Daase, Lars Jonas Bollmeier, Lawrence Benson, and Tilmann Rabl. 2021. Maximizing persistent memory bandwidth utilization for OLAP workloads. In SIGMOD. ACM, Virtual Event, China, 339--351."},{"key":"e_1_2_1_10_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. ACM, Portland, Oregon, USA , 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. ACM, Portland, Oregon, USA, 969--984."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_12_1","volume-title":"SIGMOD. ACM","author":"Galakatos Alex","unstructured":"Alex Galakatos , Michael Markovitch , Carsten Binnig , Rodrigo Fonseca , and Tim Kraska . 2019. FITing-Tree: A data-aware index structure . In SIGMOD. ACM , Amsterdam, The Netherlands , 1189--1206. Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. FITing-Tree: A data-aware index structure. In SIGMOD. ACM, Amsterdam, The Netherlands, 1189--1206."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436921"},{"key":"e_1_2_1_14_1","volume-title":"Endurable transient inconsistency in byte-addressable persistent B+-tree","author":"Hwang Deukyeon","unstructured":"Deukyeon Hwang , Wook-Hee Kim , Youjip Won , and Beomseok Nam . 2018. Endurable transient inconsistency in byte-addressable persistent B+-tree . In FAST. USENIX Association , Oakland, CA, USA , 187--200. Deukyeon Hwang, Wook-Hee Kim, Youjip Won, and Beomseok Nam. 2018. Endurable transient inconsistency in byte-addressable persistent B+-tree. In FAST. USENIX Association, Oakland, CA, USA, 187--200."},{"key":"e_1_2_1_15_1","volume-title":"Xinwei Fu, Sanidhya Kashyap, and Changwoo Min.","author":"Kim Wook-Hee","year":"2021","unstructured":"Wook-Hee Kim , Madhava Krishnan Ramanathan , Xinwei Fu, Sanidhya Kashyap, and Changwoo Min. 2021 . PACTree: A high performance persistent range index using PAC guidelines. In SOSP. ACM, Virtual Event \/ Koblenz, Germany , 424--439. Wook-Hee Kim, Madhava Krishnan Ramanathan, Xinwei Fu, Sanidhya Kashyap, and Changwoo Min. 2021. PACTree: A high performance persistent range index using PAC guidelines. In SOSP. ACM, Virtual Event \/ Koblenz, Germany, 424--439."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129263"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"RadixSpline: A single-pass learned index. In aiDM@SIGMOD. ACM, Portland","volume":"5","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 aiDM@SIGMOD. ACM, Portland , Oregon, USA , 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. ACM, Portland, Oregon, USA, 5:1--5:5.","journal-title":"Oregon, USA"},{"key":"e_1_2_1_18_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. ACM, Houston, TX, USA , 489--504. Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In SIGMOD. ACM, Houston, TX, USA, 489--504."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3009498"},{"key":"e_1_2_1_20_1","volume-title":"Recipe: Converting concurrent DRAM indexes to persistent-memory indexes. In SOSP. ACM, Huntsville, ON, Canada, 462--477.","author":"Lee Se Kwon","year":"2019","unstructured":"Se Kwon Lee , Jayashree Mohan , Sanidhya Kashyap , Taesoo Kim , and Vijay Chidambaram . 2019 . Recipe: Converting concurrent DRAM indexes to persistent-memory indexes. In SOSP. ACM, Huntsville, ON, Canada, 462--477. Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, and Vijay Chidambaram. 2019. Recipe: Converting concurrent DRAM indexes to persistent-memory indexes. In SOSP. ACM, Huntsville, ON, Canada, 462--477."},{"key":"e_1_2_1_21_1","first-page":"73","article-title":"Optimistic lock coupling: A scalable and efficient general-purpose synchronization method","volume":"42","author":"Leis Viktor","year":"2019","unstructured":"Viktor Leis , Michael Haubenschild , and Thomas Neumann . 2019 . Optimistic lock coupling: A scalable and efficient general-purpose synchronization method . IEEE Data Eng. Bull. 42 , 1 (2019), 73 -- 84 . Viktor Leis, Michael Haubenschild, and Thomas Neumann. 2019. Optimistic lock coupling: A scalable and efficient general-purpose synchronization method. IEEE Data Eng. Bull. 42, 1 (2019), 73--84.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"The ART of practical synchronization. In DaMoN. ACM, San Francisco","volume":"3","author":"Leis Viktor","year":"2016","unstructured":"Viktor Leis , Florian Scheibner , Alfons Kemper , and Thomas Neumann . 2016 . The ART of practical synchronization. In DaMoN. ACM, San Francisco , CA, USA , 3 : 1 -- 3 :8. Viktor Leis, Florian Scheibner, Alfons Kemper, and Thomas Neumann. 2016. The ART of practical synchronization. In DaMoN. ACM, San Francisco, CA, USA, 3:1--3:8.","journal-title":"CA, USA"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384355"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494141"},{"key":"e_1_2_1_26_1","volume-title":"TLBtree: A read\/write-optimized tree index for non-volatile memory","author":"Luo Yongping","year":"1889","unstructured":"Yongping Luo , Peiquan Jin , Qinglin Zhang , and Bin Cheng . 2021. TLBtree: A read\/write-optimized tree index for non-volatile memory . In ICDE. IEEE Computer Society , Chania, Greece , 1889 --1894. Yongping Luo, Peiquan Jin, Qinglin Zhang, and Bin Cheng. 2021. TLBtree: A read\/write-optimized tree index for non-volatile memory. In ICDE. IEEE Computer Society, Chania, Greece, 1889--1894."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3476981"},{"key":"e_1_2_1_28_1","volume-title":"ROART: Range-query optimized persistent","author":"Ma Shaonan","year":"2021","unstructured":"Shaonan Ma , Kang Chen , Shimin Chen , Mengxing Liu , Jianglang Zhu , Hongbo Kang , and Yongwei Wu . 2021 . ROART: Range-query optimized persistent ART. In FAST. USENIX Association , Indianapolis, Indiana , 1--16. Shaonan Ma, Kang Chen, Shimin Chen, Mengxing Liu, Jianglang Zhu, Hongbo Kang, and Yongwei Wu. 2021. ROART: Range-query optimized persistent ART. In FAST. USENIX Association, Indianapolis, Indiana, 1--16."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-022-04394-7"},{"key":"e_1_2_1_30_1","first-page":"368","article-title":"Evaluating In-Memory Hash Joins on Persistent Memory","volume":"2","author":"Maltenberger Tobias","year":"2022","unstructured":"Tobias Maltenberger , Till Lehmann , Lawrence Benson , and Tilmann Rabl . 2022 . Evaluating In-Memory Hash Joins on Persistent Memory . In EDBT. 2 : 368 -- 362 :372. Tobias Maltenberger, Till Lehmann, Lawrence Benson, and Tilmann Rabl. 2022. Evaluating In-Memory Hash Joins on Persistent Memory. In EDBT. 2:368--2:372.","journal-title":"EDBT."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_33_1","volume-title":"SIGMOD","author":"Oukid Ismail","unstructured":"Ismail Oukid , Johan Lasperas , Anisoara Nica , Thomas Willhalm , and Wolfgang Lehner . 2016. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory . In SIGMOD . ACM , San Francisco, CA, USA , 371--386. Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. 2016. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In SIGMOD. ACM, San Francisco, CA, USA, 371--386."},{"key":"e_1_2_1_34_1","volume-title":"ICLR. OpenReview.net","author":"Shazeer Noam","unstructured":"Noam Shazeer , Azalia Mirhoseini , Krzysztof Maziarz , Andy Davis , Quoc V. Le , Geoffrey E. Hinton , and Jeff Dean . 2017. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer . In ICLR. OpenReview.net , Toulon, France . Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc V. Le, Geoffrey E. Hinton, and Jeff Dean. 2017. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In ICLR. OpenReview.net, Toulon, France."},{"key":"e_1_2_1_35_1","volume-title":"PPoPP. ACM","author":"Tang Chuzhe","unstructured":"Chuzhe Tang , Youyun Wang , Zhiyuan Dong , Gansen Hu , Zhaoguo Wang , Minjie Wang , and Haibo Chen . 2020. XIndex: A scalable learned index for multicore data storage . In PPoPP. ACM , San Diego , California, USA , 308--320. Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang, Minjie Wang, and Haibo Chen. 2020. XIndex: A scalable learned index for multicore data storage. In PPoPP. ACM, San Diego, California, USA, 308--320."},{"key":"e_1_2_1_36_1","volume-title":"Campbell","author":"Venkataraman Shivaram","year":"2011","unstructured":"Shivaram Venkataraman , Niraj Tolia , Parthasarathy Ranganathan , and Roy H . Campbell . 2011 . Consistent and durable data structures for non-volatile byte-addressable memory. In FAST. USENIX Association , San Jose, CA, USA, 61--75. Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. 2011. Consistent and durable data structures for non-volatile byte-addressable memory. In FAST. USENIX Association, San Jose, CA, USA, 61--75."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732277"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0355-0"},{"key":"e_1_2_1_40_1","volume-title":"An empirical guide to the behavior and use of scalable persistent memory","author":"Yang Jian","unstructured":"Jian Yang , Juno Kim , Morteza Hoseinzadeh , Joseph Izraelevitz , and Steven Swanson . 2020. An empirical guide to the behavior and use of scalable persistent memory . In FAST. USENIX Association , Santa Clara, CA, USA , 169--182. Jian Yang, Juno Kim, Morteza Hoseinzadeh, Joseph Izraelevitz, and Steven Swanson. 2020. An empirical guide to the behavior and use of scalable persistent memory. In FAST. USENIX Association, Santa Clara, CA, USA, 169--182."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2479621"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-021-1348-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2019.2925366"},{"key":"e_1_2_1_44_1","volume-title":"Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory. In SIGMOD. 2195--2207.","author":"Zhou Xinjing","year":"2021","unstructured":"Xinjing Zhou , Joy Arulraj , Andrew Pavlo , and David Cohen . 2021 . Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory. In SIGMOD. 2195--2207. Xinjing Zhou, Joy Arulraj, Andrew Pavlo, and David Cohen. 2021. Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory. In SIGMOD. 2195--2207."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372717"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317858"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3565816.3565826","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:33:43Z","timestamp":1672220023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3565816.3565826"}},"subtitle":["a persistent learned index for non-volatile memory with high performance and instant recovery"],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.14778\/3565816.3565826"],"URL":"https:\/\/doi.org\/10.14778\/3565816.3565826","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"2022-11-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}