{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:04Z","timestamp":1755900604437,"version":"3.44.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Graduate Fellowships for Science, Technology, Engineering, and Mathematics Diversity","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and data management applications. The classical algorithm for this problem, dating back to 1981, has amortized cost O(log bn). Subsequent work has led to improvements in three directions: low-latency (worst-case) bounds; high-throughput (expected) bounds; and (adaptive) bounds for important workloads.<\/jats:p>\n          <jats:p>Perhaps surprisingly, these three directions of research have remained almost entirely disjoint---this is because, so far, the techniques that allow for progress in one direction have forced worsening bounds in the others. Thus there would appear to be a tension between worst-case, adaptive, and expected bounds. List labeling has been proposed for use in databases at least as early as PODS'99, but a database needs good throughput, response time, and needs to adapt to common workloads (e.g., bulk loads), and no current list-labeling algorithm achieve good bounds for all three.<\/jats:p>\n          <jats:p>We show that this tension is not fundamental. In fact, with the help of new data-structural techniques, one can actually combine any three list-labeling solutions in order to cherry-pick the best worst-case, adaptive, and expected bounds from each of them.<\/jats:p>","DOI":"10.1145\/3651602","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-19","source":"Crossref","is-referenced-by-count":0,"title":["Layered List Labeling"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University and RelationalAI, Stony Brook, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4890-7413","authenticated-orcid":false,"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5522-9193","authenticated-orcid":false,"given":"Hanna","family":"Koml\u00f3s","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51542-9_33"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--52846--6_82"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117458"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902276"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_16"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_17"},{"volume-title":"Proc. 10th European Symposium on Algorithms (ESA). 152--164","author":"Bender Michael A.","key":"e_1_2_1_7_1","unstructured":"Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and J. Zito. 2002 c. Two Simplified Algorithms for Maintaining Order in a List. In Proc. 10th European Symposium on Algorithms (ESA). 152--164."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00096"},{"key":"e_1_2_1_9_1","volume-title":"2005 a. Cache-Oblivious B-Trees. sicomp","author":"Bender M. A.","year":"2005","unstructured":"M. A. Bender, E. Demaine, and M. Farach-Colton. 2005 a. Cache-Oblivious B-Trees. sicomp, Vol. 35, 2 (2005), 341--358."},{"key":"e_1_2_1_10_1","volume-title":"Cache-oblivious B-trees. In Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 399--409","author":"Bender Michael A","year":"2000","unstructured":"Michael A Bender, Erik D Demaine, and Martin Farach-Colton. 2000. Cache-oblivious B-trees. In Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 399--409."},{"key":"e_1_2_1_11_1","volume-title":"Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 29--38","author":"Bender Michael A.","year":"2002","unstructured":"Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu. 2002 d. A Locality-Preserving Cache-Oblivious Dynamic Dictionary. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 29--38."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2907945"},{"volume-title":"Proc. 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM, 233--242","author":"Bender Michael A.","key":"e_1_2_1_13_1","unstructured":"Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul. 2006 a. Cache-oblivious string B-trees. In Proc. 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM, 233--242."},{"key":"e_1_2_1_14_1","unstructured":"Michael A. Bender Martin Farach-Colton and Miguel Mosteiro. 2004. Insertion Sort is $O(n log n)$. In Fun with Algorithms. 16--23."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1237-z"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.98"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292616"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 39--48","author":"Brodal Gerth St\u00f8lting","year":"2002","unstructured":"Gerth St\u00f8lting Brodal, Rolf Fagerberg, and Riko Jacob. 2002. Cache oblivious search trees via binary trees of small height. In Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 39--48."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214083"},{"key":"e_1_2_1_21_1","volume-title":"Proc. International Colloquium on Automata, Languages, and Programming (ICALP) (Lecture Notes in Computer Science","volume":"302","author":"Jan Bul\u00e1","unstructured":"Jan Bul\u00e1 nek, Michal Kouck\u00fd , and Michael E. Saks. 2013. On Randomized Online Labeling with Polynomially Many Labels. In Proc. International Colloquium on Automata, Languages, and Programming (ICALP) (Lecture Notes in Computer Science, Vol. 7965). Springer, 291--302."},{"key":"e_1_2_1_22_1","volume-title":"Proc. 25th European Symposium on Algorithms (ESA). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Devanny William E","year":"2017","unstructured":"William E Devanny, Jeremy T Fineman, Michael T Goodrich, and Tsvi Kopelowitz. 2017. The online house numbering problem: Min-max online list labeling. In Proc. 25th European Symposium on Algorithms (ESA). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802184"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58218-5_12"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100315808"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52846-6_87"},{"key":"e_1_2_1_27_1","volume-title":"Rivest","author":"Galperin Igal","year":"1993","unstructured":"Igal Galperin and Ronald L. Rivest. 1993. Scapegoat Trees. In Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM\/SIAM, 165--174."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36136-7_21"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1140-z"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.07.001"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10843-2_34"},{"key":"e_1_2_1_32_1","unstructured":"Irit Katriel. 2002. Implicit Data Structures Based on Local Reorganizations. Master's thesis. Technion -- Israel Inst. of Tech. Haifa."},{"key":"e_1_2_1_33_1","first-page":"1","article-title":"Fast Concurrent Reads and Updates with PMAs. In Proceedings of the 2nd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)","volume":"8","author":"Leo Dean De","year":"2019","unstructured":"Dean De Leo and Peter A. Boncz. 2019. Fast Concurrent Reads and Updates with PMAs. In Proceedings of the 2nd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). ACM, 8:1--8:8.","journal-title":"ACM"},{"key":"e_1_2_1_34_1","volume-title":"Teseo and the Analysis of Structural Dynamic Graphs. Proc. VLDB Endowment 14","volume":"14","author":"Leo Dean De","year":"2021","unstructured":"Dean De Leo and Peter A. Boncz. 2021. Teseo and the Analysis of Structural Dynamic Graphs. Proc. VLDB Endowment 14, Vol. 14, 6 (2021), 1053--1066."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2305.10536"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258638"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457313"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304009"},{"key":"e_1_2_1_40_1","volume-title":"Lower Bounds and Open Questions. In International Computer Science Symposium in Russia (CSR)","volume":"10846","author":"Saks Michael","year":"2018","unstructured":"Michael Saks. 2018. Online Labeling: Algorithms, Lower Bounds and Open Questions. In International Computer Science Symposium in Russia (CSR), Vol. 10846. Springer, 23--28."},{"key":"e_1_2_1_41_1","unstructured":"Tokutek Inc. 2015a. TokuDB: MySQL Performance MariaDB Performance. http:\/\/www.tokutek.com\/products\/tokudb-for-mysql\/."},{"key":"e_1_2_1_42_1","unstructured":"Tokutek Inc. 2015b. TokuMX--MongoDB Performance Engine. http:\/\/www.tokutek.com\/products\/tokumx-for-mongodb\/."},{"volume-title":"Streaming Sparse Graphs using Efficient Dynamic Sets","author":"Wheatman Brian","key":"e_1_2_1_43_1","unstructured":"Brian Wheatman and Randal Burns. 2021. Streaming Sparse Graphs using Efficient Dynamic Sets. In IEEE BigData. IEEE, 284--294."},{"volume-title":"Packed Compressed Sparse Row: A Dynamic Graph Representation","author":"Wheatman Brian","key":"e_1_2_1_44_1","unstructured":"Brian Wheatman and Helen Xu. 2018. Packed Compressed Sparse Row: A Dynamic Graph Representation. In HPEC. IEEE, 1--7."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976472.3"},{"key":"e_1_2_1_46_1","unstructured":"Dan E. Willard. 1981. Inserting and Deleting Records in Blocked Sequential Files. Technical Report TM81--45193--5. Bell Labs Tech Reports."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802183"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16879"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90034-D"},{"volume-title":"Density control and on-line labeling problems. Ph.,D. Dissertation","author":"Zhang Ju","key":"e_1_2_1_50_1","unstructured":"Ju Zhang. 1993. Density control and on-line labeling problems. Ph.,D. Dissertation. University of Rochester."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:01Z","timestamp":1755898741000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651602"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651602"],"URL":"https:\/\/doi.org\/10.1145\/3651602","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}