{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T22:41:08Z","timestamp":1780094468591,"version":"3.54.0"},"reference-count":145,"publisher":"Association for Computing Machinery (ACM)","issue":"11","funder":[{"name":"NSF","award":["IIS-1910216"],"award-info":[{"award-number":["IIS-1910216"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>Skiplists have become prevalent in systems. The main advantages of skiplists are their simplicity and ease of implementation, and the ability to support operations in the same asymptotic complexities as their tree-based counterparts. In this survey, we explore skiplists and their many variants. We highlight many scenarios about how skiplists are useful, and how they fit well in these usage scenarios. We also compare skiplists with other data structures, especially tree-based structures. Extensions to skiplists include structural modifications, as well as algorithmic enhancements and operations. We categorize the existing extensions, and summarize the skiplist variants that belong to each category. We present how data systems incorporate skiplist variants into many different application scenarios to serve various purposes. These data systems cover a wide range of applications, from data indexing to block-chain, from network algorithms to deterministic skiplists, and so on. It illustrates an impactful and diverse applications of skiplists in various domains of data systems.<\/jats:p>","DOI":"10.1145\/3736754","type":"journal-article","created":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T11:17:51Z","timestamp":1747912671000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Data Systems"],"prefix":"10.1145","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-4369-4440","authenticated-orcid":false,"given":"Lu","family":"Xing","sequence":"first","affiliation":[{"name":"Computer Science, Purdue University, West Lafayette, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1954-8576","authenticated-orcid":false,"given":"Venkata Sai Pavan Kumar","family":"Vadrevu","sequence":"additional","affiliation":[{"name":"Computer Science, Purdue University, West Lafayette, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8169-7775","authenticated-orcid":false,"given":"Walid G.","family":"Aref","sequence":"additional","affiliation":[{"name":"Computer Science, Purdue University, West Lafayette, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,11]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"A kernel skiplist implementation. Retrieved October 9 2023 from https:\/\/lwn.net\/Articles\/551896\/"},{"key":"e_1_3_1_3_2","unstructured":"The MuQSS CPU scheduler. Retrieved October 9 2023 from https:\/\/lwn.net\/Articles\/720227\/"},{"key":"e_1_3_1_4_2","unstructured":"Skiplists for Range Indexes. Retrieved October 9 2023 from https:\/\/lwn.net\/Articles\/549470\/"},{"key":"e_1_3_1_5_2","unstructured":"SingleStore. Retrieved October 10 2023 from https:\/\/www.singlestore.com\/"},{"key":"e_1_3_1_6_2","unstructured":"Apache HBase. Retrieved January 9 2024 https:\/\/hbase.apache.org\/"},{"key":"e_1_3_1_7_2","unstructured":"Redis. Retrieved January 9 2024 https:\/\/redis.io\/"},{"key":"e_1_3_1_8_2","unstructured":"RocksDB. Retrieved January 9 2024 https:\/\/github.com\/facebook\/rocksdb"},{"key":"e_1_3_1_9_2","unstructured":"PMem-RocksDB. Retrieved December 10 2024 from https:\/\/github.com\/pmem\/pmem-rocksdb"},{"key":"e_1_3_1_10_2","unstructured":"A fork of LevelDB intended to meet the needs of HyperDex while remaining compatible with LevelDB. Retrieved December 12 2024 from https:\/\/github.com\/rescrv\/HyperLevelDB"},{"key":"e_1_3_1_11_2","unstructured":"LMDB. Retrieved December 12 2024 from https:\/\/www.symas.com\/mdb"},{"key":"e_1_3_1_12_2","unstructured":"WiredTiger. Retrieved December 12 2024 from https:\/\/github.com\/wiredtiger\/wiredtiger"},{"key":"e_1_3_1_13_2","unstructured":"Linked List History. Retrieved December 20 2024 from https:\/\/en.wikipedia.org\/wiki\/Linked_list#History"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0229-0"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687669"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-022-00441-x"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688523"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3164147"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290674"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484254"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1138-6"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064193"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Dmitry Basin Edward Bortnikov Anastasia Braginsky Guy Golan-Gueta Eshcar Hillel Idit Keidar and Moshe Sulamy. 2017. Kiwi: A key-value map for scalable real-time analytics. 52 8 (2017) 357\u2013369.","DOI":"10.1145\/3155284.3018761"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1734663.1734671"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056117"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223785"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/319996.319998"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_3"},{"key":"e_1_3_1_29_2","first-page":"1106","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bose Prosenjit","year":"2008","unstructured":"Prosenjit Bose, Karim Dou\u00efeb, and Stefan Langerman. 2008. Dynamic optimality for skip lists and B-trees. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Citeseer, 1106\u20131114."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693488"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_3"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25873-2_15"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-019-02925-1"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","unstructured":"Seonghun Cho and Sartaj Sahni. 1998. Weight-biased leftist trees and modified skip lists. ACM J. Exp. Algorithmics 3 (September 1998) 2-es. DOI:10.1145\/297096.297111","DOI":"10.1145\/297096.297111"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538591"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323191"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461819"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181945"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186816"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89335-6_12"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2013.42"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/98457.98525"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1233341.1233413"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3876"},{"key":"e_1_3_1_47_2","first-page":"33","volume-title":"Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST 21)","author":"Dong Siying","year":"2021","unstructured":"Siying Dong, Andrew Kryczka, Yanqin Jin, and Michael Stumm. 2021. Evolution of development priorities in key-value stores serving large-scale applications: The \\(\\lbrace\\) RocksDB \\(\\rbrace\\) experience. In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST 21). 33\u201349."},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325933"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064138"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44808-X_18"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011776"},{"key":"e_1_3_1_52_2","volume-title":"Practical Lock-freedom","author":"Fraser Keir","year":"2004","unstructured":"Keir Fraser. 2004. Practical Lock-freedom. Technical Report. University of Cambridge, Computer Laboratory."},{"key":"e_1_3_1_53_2","unstructured":"Chunkai Fu Jung Hoon Seo and Samson Zhou. 2024. Learning-augmented skip lists. arXiv:2402.10457. Retrieved from https:\/\/arxiv.org\/abs\/2402.10457 (2024)."},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2019.00015"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453962"},{"key":"e_1_3_1_56_2","unstructured":"Sanjay Ghemawat and Jeff Dean. 2011. LevelDB. Retrieved May 29 2025 https:\/\/github.com\/google\/leveldb"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"issue":"1","key":"e_1_3_1_58_2","first-page":"1","article-title":"TeksDB: Weaving data structures for a high-performance key-value store","volume":"3","author":"Han Youil","year":"2019","unstructured":"Youil Han, Bryan Kim, Jeseong Yeon, Sungjin Lee, and Eunji Lee. 2019. TeksDB: Weaving data structures for a high-performance key-value store. Proc. of ACM on Measurement and Analysis of Computing Systems 3, 1 (2019), 1\u201323.","journal-title":"Proc. of ACM on Measurement and Analysis of Computing Systems"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028258"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.485644"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(96)00015-4"},{"key":"e_1_3_1_62_2","volume-title":"Transactional Memory","author":"Harris Tim","year":"2022","unstructured":"Tim Harris, James Larus, and Ravi Rajwar. 2022. Transactional Memory. Springer Nature."},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45414-4_21"},{"key":"e_1_3_1_64_2","unstructured":"Nicholas J. A. Harvey Michael B. Jones Stefan Saroiu Marvin Theimer and Alec Wolman. 2003. SkipNet: A scalable overlay network with practical locality properties. In Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems - Volume 4 (USITS\u201903). USENIX Association USA 9."},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872057"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810540"},{"key":"e_1_3_1_67_2","first-page":"103","volume-title":"Proceedings of the Conference On Principles of Distributed Systems (OPODIS). Citeseer","author":"Herlihy Maurice","year":"2006","unstructured":"Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. 2006. A provably correct scalable concurrent skip list. In Proceedings of the Conference On Principles of Distributed Systems (OPODIS). Citeseer. 103."},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72951-8_11"},{"key":"e_1_3_1_69_2","volume-title":"The art of Multiprocessor Programming","author":"Herlihy Maurice","year":"2020","unstructured":"Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear. 2020. The art of Multiprocessor Programming. Newnes."},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-020-0126-6"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314041"},{"key":"e_1_3_1_72_2","first-page":"187","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST 18)","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 18). 187\u2013200."},{"key":"e_1_3_1_73_2","unstructured":"Joseph Izraelevitz Jian Yang Lu Zhang Juno Kim Xiao Liu Amirsaman Memaripour Yun Joon Soh Zixuan Wang Yi Xu Subramanya R Dulloor Jishen Zhao and Steven Swanson. 2019. Basic performance measurements of the intel optane DC persistent memory module. arXiv:1903.05714. Retrieved from https:\/\/arxiv.org\/abs\/1903.05714 (2019)."},{"key":"e_1_3_1_74_2","first-page":"191","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST 19)","author":"Kaiyrakhmet Olzhas","year":"2019","unstructured":"Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H Noh, and Young-ri Choi. 2019. SLM-DB:Single-LevelKey-value store with persistent memory. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST 19). 191\u2013205."},{"key":"e_1_3_1_75_2","first-page":"437","volume-title":"Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC 16)","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David G Andersen. 2016. Design guidelines for high performance \\(\\lbrace\\) RDMA \\(\\rbrace\\) systems. In Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC 16). 437\u2013450."},{"key":"e_1_3_1_76_2","first-page":"993","volume-title":"Proceedings of the 2018 USENIX ATC","author":"Kannan Sudarsun","year":"2018","unstructured":"Sudarsun Kannan, Nitish Bhat, Ada Gavrilovska, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2018. Redesigning LSMs for nonvolatile memory with NoveLSM. In Proceedings of the 2018 USENIX ATC. 993\u20131005."},{"key":"e_1_3_1_77_2","unstructured":"Marios Kardaras Dimitrios Siakavaras Konstantinos Nikas Georgios Goumas and Nectarios Koziris. 2018. Fast Concurrent Skip Lists with HTM."},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452783"},{"key":"e_1_3_1_80_2","first-page":"161","volume-title":"Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)","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 the 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 161\u2013177."},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483589"},{"key":"e_1_3_1_82_2","volume-title":"The Art of Computer Programming","author":"Knuth Donald Ervin","year":"1997","unstructured":"Donald Ervin Knuth. 1997. The Art of Computer Programming. Vol. 3. Pearson Education."},{"key":"e_1_3_1_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508437"},{"key":"e_1_3_1_84_2","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007278"},{"key":"e_1_3_1_85_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508834.2513149"},{"key":"e_1_3_1_86_2","unstructured":"Michael Lamoureux and Bradford Nickerson1996. On the equivalence of b-trees and deterministic skip list. (1996)."},{"key":"e_1_3_1_87_2","doi-asserted-by":"publisher","DOI":"10.5555\/2697438.2697659"},{"key":"e_1_3_1_88_2","unstructured":"Doug Lea. Accessed on Jan 7 2024. ConcurrentSkipListMap. Retrieved from https:\/\/github.com\/openjdk-mirror\/jdk7u-jdk\/blob\/master\/src\/share\/classes\/java\/util\/concurrent\/ConcurrentSkipListMap.java"},{"key":"e_1_3_1_89_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19063-7_64"},{"key":"e_1_3_1_90_2","first-page":"257","volume-title":"Proceedings of the 15th USENIX Conference on File and Storage Technologies","author":"Lee Se Kwon","year":"2017","unstructured":"Se Kwon Lee, K Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H Noh. 2017. WORT: Write optimal radix tree for persistent memory storage systems. In Proceedings of the 15th USENIX Conference on File and Storage Technologies. 257\u2013270."},{"key":"e_1_3_1_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359635"},{"key":"e_1_3_1_92_2","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319663"},{"key":"e_1_3_1_93_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_3_1_94_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_3_1_95_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920990"},{"key":"e_1_3_1_96_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3173707"},{"key":"e_1_3_1_97_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064015"},{"key":"e_1_3_1_98_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_15"},{"key":"e_1_3_1_99_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087582"},{"key":"e_1_3_1_100_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_3_1_101_2","doi-asserted-by":"publisher","DOI":"10.1109\/PDGC.2012.6449835"},{"key":"e_1_3_1_102_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_1_103_2","doi-asserted-by":"publisher","DOI":"10.1145\/356643.356645"},{"key":"e_1_3_1_104_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67952-5_11"},{"key":"e_1_3_1_105_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2012.18"},{"key":"e_1_3_1_106_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2017.13"},{"key":"e_1_3_1_107_2","doi-asserted-by":"publisher","DOI":"10.5555\/139404.139478"},{"key":"e_1_3_1_108_2","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236412"},{"key":"e_1_3_1_109_2","volume-title":"Skip List Data Structures for Multidimensional Data","author":"Nickerson Bradford G.","year":"1998","unstructured":"Bradford G. Nickerson. 1998. Skip List Data Structures for Multidimensional Data. Technical Report."},{"key":"e_1_3_1_110_2","doi-asserted-by":"crossref","unstructured":"Rizal Mohd Nor Mikhail Nesterenko and Christian Scheideler. 2011. Corona: A stabilizing deterministic message-passing skip list. In Stabilization Safety and Security of Distributed Systems Springer Berlin Heidelberg Berlin Heidelberg 356\u2013370.","DOI":"10.1007\/978-3-642-24550-3_27"},{"key":"e_1_3_1_111_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31500-9_4"},{"key":"e_1_3_1_112_2","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170081"},{"key":"e_1_3_1_113_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_3_1_114_2","volume-title":"Proceedings of the CIDR","author":"Oukid Ismail","year":"2015","unstructured":"Ismail Oukid, Wolfgang Lehner, Thomas Kissinger, Thomas Willhalm, and Peter Bumbulis. 2015. Instant recovery for main memory databases.. In Proceedings of the CIDR."},{"key":"e_1_3_1_115_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_1_116_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_1_117_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00157"},{"key":"e_1_3_1_118_2","doi-asserted-by":"publisher","DOI":"10.5555\/93717"},{"key":"e_1_3_1_119_2","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_3_1_120_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_3_1_121_2","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335449"},{"key":"e_1_3_1_122_2","unstructured":"D. P. Reed. 1978. Naming and Synchronization in a Decentralized Computer System. Technical Report. Massachusetts Institute of Technology USA."},{"key":"e_1_3_1_123_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISPDC.2015.32"},{"key":"e_1_3_1_124_2","doi-asserted-by":"publisher","unstructured":"Konstantinos Sagonas and Kjell Winblad. 2018. A contention adapting approach to concurrent ordered sets. Journal of Parallel and Distributed Computing 115 (2018) 1\u201319. DOI:10.1016\/j.jpdc.2017.11.007","DOI":"10.1016\/j.jpdc.2017.11.007"},{"key":"e_1_3_1_125_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_1_126_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2000.845994"},{"key":"e_1_3_1_127_2","doi-asserted-by":"publisher","unstructured":"Bikash Chandra Singh Qingqing Ye Haibo Hu and Bin Xiao. 2023. Efficient and lightweight indexing approach for multi-dimensional historical data in blockchain. Future Generation Computer Systems 139 (2023) 210\u2013223. DOI:10.1016\/j.future.2022.09.002","DOI":"10.1016\/j.future.2022.09.002"},{"key":"e_1_3_1_128_2","doi-asserted-by":"publisher","unstructured":"Ramesh Singh Sandip Chakraborty and Sushanta Karmakar. 2015. Concurrent deterministic 1\u20132 skip list in distributed message passing systems. Int. J. Parallel Emerg. Distrib. Syst. 30 2 (March 2015) 135\u2013174. DOI:10.1080\/17445760.2013.876637","DOI":"10.1080\/17445760.2013.876637"},{"key":"e_1_3_1_129_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_1_130_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56111-0_1"},{"key":"e_1_3_1_131_2","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968188"},{"key":"e_1_3_1_132_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.12.005"},{"key":"e_1_3_1_133_2","volume-title":"Operating Systems: Design and Implementation","author":"Tanenbaum Andrew S","year":"1997","unstructured":"Andrew S Tanenbaum and Albert S Woodhull. 1997. Operating Systems: Design and Implementation. Vol. 68. Prentice Hall Englewood Cliffs."},{"key":"e_1_3_1_134_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICME.2006.262800"},{"key":"e_1_3_1_135_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70748"},{"key":"e_1_3_1_136_2","doi-asserted-by":"publisher","DOI":"10.1145\/3063955.3063978"},{"key":"e_1_3_1_137_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460874"},{"key":"e_1_3_1_138_2","volume-title":"Algorithms + Data Structures=programs","author":"Wirth Niklaus","year":"1976","unstructured":"Niklaus Wirth. 1976. Algorithms + Data Structures=programs. Vol. 158. Prentice-Hall Englewood Cliffs, NJ."},{"key":"e_1_3_1_139_2","doi-asserted-by":"publisher","DOI":"10.1145\/1275986.1275991"},{"key":"e_1_3_1_140_2","doi-asserted-by":"publisher","unstructured":"Renzhi Xiao Dan Feng Yuchong Hu Fang Wang Xueliang Wei Xiaomin Zou and Mengya Lei. 2021. Write-optimized and consistent skiplists for non-volatile memory. IEEE Access 9 (2021) 69850\u201369859. DOI:10.1109\/ACCESS.2021.3077898","DOI":"10.1109\/ACCESS.2021.3077898"},{"key":"e_1_3_1_141_2","unstructured":"Zhongle Xie Qingchao Cai HV Jagadish Beng Chin Ooi and Weng-Fai Wong. 2016. PI: A parallel in-memory skip list based index. arXiv:1601.00159. Retrieved from https:\/\/arxiv.org\/abs\/1601.00159 (2016)."},{"key":"e_1_3_1_142_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.54"},{"key":"e_1_3_1_143_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386708"},{"key":"e_1_3_1_144_2","doi-asserted-by":"publisher","DOI":"10.1145\/3423211.3425672"},{"key":"e_1_3_1_145_2","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352134"},{"key":"e_1_3_1_146_2","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736754","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T12:54:02Z","timestamp":1749646442000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736754"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,11]]},"references-count":145,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3736754"],"URL":"https:\/\/doi.org\/10.1145\/3736754","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,11]]},"assertion":[{"value":"2024-03-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}