{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:03:57Z","timestamp":1787389437666,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055437","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"1081-1093","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["DecreaseKeys are expensive for external memory priority queues"],"prefix":"10.1145","author":[{"given":"Kasper","family":"Eenberg","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_2_2_1","first-page":"58","volume-title":"Proc. 7th ACM\/SIAM Symposium on Discrete Algorithms, SODA \u201996","author":"Brodal G. S.","year":"1996","unstructured":"G. S. Brodal . Worst-case efficient priority queues . In Proc. 7th ACM\/SIAM Symposium on Discrete Algorithms, SODA \u201996 , pages 52\u2013 58 , 1996 . G. S. Brodal. Worst-case efficient priority queues. In Proc. 7th ACM\/SIAM Symposium on Discrete Algorithms, SODA \u201996, pages 52\u201358, 1996."},{"key":"e_1_3_2_2_3_1","first-page":"554","volume-title":"Proc. 14th ACM\/SIAM Symposium on Discrete Algorithms, SODA \u201903","author":"Brodal G. S.","year":"2003","unstructured":"G. S. Brodal and R. Fagerberg . Lower bounds for external memory dictionaries . In Proc. 14th ACM\/SIAM Symposium on Discrete Algorithms, SODA \u201903 , pages 546\u2013 554 , 2003 . G. S. Brodal and R. Fagerberg. Lower bounds for external memory dictionaries. In Proc. 14th ACM\/SIAM Symposium on Discrete Algorithms, SODA \u201903, pages 546\u2013554, 2003."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611501"},{"key":"e_1_3_2_2_5_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990","unstructured":"T. H. Cormen , C. E. Leiserson , and R. L. Rivest . Introduction to Algorithms . The MIT Press , Cambridge, Mass ., 1990 . T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Mass., 1990."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00006-7"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509993"},{"key":"e_1_3_2_2_9_1","first-page":"144","volume-title":"Proc. 43rd IEEE Symposium on Foundations of Computer Science","author":"Han Y.","year":"2002","unstructured":"Y. Han and M. Thorup . Integer sorting in O (n lg lg n) expected time and linear space . In Proc. 43rd IEEE Symposium on Foundations of Computer Science , pages 135\u2013 144 , 2002 . Y. Han and M. Thorup. Integer sorting in O (n lg lg n) expected time and linear space. In Proc. 43rd IEEE Symposium on Foundations of Computer Science, pages 135\u2013144, 2002."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095164"},{"key":"e_1_3_2_2_11_1","first-page":"1996","volume-title":"Proc. 8th IEEE Symposium on Parallel and Distributed Processing, SPDP \u201996","author":"Kumar V.","unstructured":"V. Kumar and E. J. Schwabe . Improved algorithms and data structures for solving graph problems in external memory . In Proc. 8th IEEE Symposium on Parallel and Distributed Processing, SPDP \u201996 , pages 169\u2013, 1996 . V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proc. 8th IEEE Symposium on Parallel and Distributed Processing, SPDP \u201996, pages 169\u2013, 1996."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_49"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.003"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314692"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806752"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_68"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873613"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055437","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:27Z","timestamp":1750220607000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":19,"alternative-id":["10.1145\/3055399.3055437","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055437","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}