{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T10:22:25Z","timestamp":1770546145284,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T00:00:00Z","timestamp":1590883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1700521"],"award-info":[{"award-number":["1700521"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,11]]},"DOI":"10.1145\/3318464.3380583","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T17:12:33Z","timestamp":1590772353000},"page":"1601-1615","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Order-Preserving Key Compression for In-Memory Search Trees"],"prefix":"10.1145","author":[{"given":"Huanchen","family":"Zhang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Xiaoxuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Michael","family":"Kaminsky","sequence":"additional","affiliation":[{"name":"BrdgAI, Pittsburgh, PA, USA"}]},{"given":"Kimberly","family":"Keeton","sequence":"additional","affiliation":[{"name":"Hewlett Packard Labs, Palo Alto, CA, USA"}]},{"given":"Andrew","family":"Pavlo","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142548"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050031"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1996.492216"},{"key":"e_1_3_2_2_4_1","volume-title":"Proceedings of ACSC'07","author":"Askitis Nikolas","year":"2007","unstructured":"Nikolas Askitis and Ranjan Sinha . 2007 . HAT-trie: a cache-conscious trie-based data structure for strings . In Proceedings of ACSC'07 . Australian Computer Society, Inc., 97--105. Nikolas Askitis and Ranjan Sinha. 2007. HAT-trie: a cache-conscious trie-based data structure for strings. In Proceedings of ACSC'07. Australian Computer Society, Inc., 97--105."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/320521.320530"},{"key":"e_1_3_2_2_6_1","volume-title":"Proceedings of VLDB'09","volume":"2","author":"Bishwaranjan","year":"2009","unstructured":"Bishwaranjan Bhattacharjee et al. 2009. Efficient index compression in DB2 LUW . Proceedings of VLDB'09 , Vol. 2 , 2 ( 2009 ), 1462--1473. Bishwaranjan Bhattacharjee et al. 2009. Efficient index compression in DB2 LUW. Proceedings of VLDB'09, Vol. 2, 2 (2009), 1462--1473."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559877"},{"key":"e_1_3_2_2_9_1","unstructured":"Matthias Boehm et al. 2011. Efficient in-memory indexing with generalized prefix trees. BTW (2011).  Matthias Boehm et al. 2011. Efficient in-memory indexing with generalized prefix trees. BTW (2011)."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375692"},{"key":"e_1_3_2_2_11_1","volume-title":"Proceedings of SoCC'10","author":"Brian","unstructured":"Brian F Cooper et al. 2010. Benchmarking cloud serving systems with YCSB . In Proceedings of SoCC'10 . ACM, 143--154. Brian F Cooper et al. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of SoCC'10. ACM, 143--154."},{"key":"e_1_3_2_2_12_1","unstructured":"Siying Dong. 2018. personal communication. 2018--12--26.  Siying Dong. 2018. personal communication. 2018--12--26."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_3_2_2_14_1","volume-title":"Foundations and Trends\u00ae in Databases","volume":"3","author":"Goetz","year":"2011","unstructured":"Goetz Graefe et al. 2011. Modern B-tree techniques . Foundations and Trends\u00ae in Databases , Vol. 3 , 4 ( 2011 ), 203--402. Goetz Graefe et al. 2011. Modern B-tree techniques. Foundations and Trends\u00ae in Databases, Vol. 3, 4 (2011), 203--402."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767867"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2236584.2236587"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Robert Lasch et al. 2019. Fast & Strong: The Case of Compressed String Dictionaries on Modern CPUs. In DaMoN'19. ACM.  Robert Lasch et al. 2019. Fast & Strong: The Case of Compressed String Dictionaries on Modern CPUs. In DaMoN'19. ACM.","DOI":"10.1145\/3329785.3329924"},{"key":"e_1_3_2_2_22_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. , Vol. 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., Vol. 42, 1 (2019), 73--84.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Viktor Leis Florian Scheibner Alfons Kemper and Thomas Neumann. 2016. The ART of practical synchronization. In DaMoN'16. ACM.  Viktor Leis Florian Scheibner Alfons Kemper and Thomas Neumann. 2016. The ART of practical synchronization. In DaMoN'16. ACM.","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737787"},{"key":"e_1_3_2_2_27_1","volume-title":"Proceedings of ICDE'19","author":"Liu Chunwei","unstructured":"Chunwei Liu , McKade Umbenhower , Hao Jiang , Pranav Subramaniam , Jihong Ma , and Aaron J. Elmore . 2019. Mostly Order Preserving Dictionaries . In Proceedings of ICDE'19 . IEEE. Chunwei Liu, McKade Umbenhower, Hao Jiang, Pranav Subramaniam, Jihong Ma, and Aaron J. Elmore. 2019. Mostly Order Preserving Dictionaries. In Proceedings of ICDE'19. IEEE."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_2_2_29_1","volume-title":"Video and Data Recording Conference","author":"Martin G","year":"1979","unstructured":"G Martin . 1979 . Range encoding: an algorithm for removing redundancy from a digitised message . In Video and Data Recording Conference , Southampton , 1979. 24--27. G Martin. 1979. Range encoding: an algorithm for removing redundancy from a digitised message. In Video and Data Recording Conference, Southampton, 1979. 24--27."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319870"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_3_2_2_32_1","volume-title":"Adaptive String Dictionary Compression in In-Memory Column-Store Database Systems. In EDBT'14","author":"M\u00fcller Ingo","year":"2014","unstructured":"Ingo M\u00fcller , Cornelius Ratsch , and Franz Faerber . 2014 . Adaptive String Dictionary Compression in In-Memory Column-Store Database Systems. In EDBT'14 . 283--294. Ingo M\u00fcller, Cornelius Ratsch, and Franz Faerber. 2014. Adaptive String Dictionary Compression in In-Memory Column-Store Database Systems. In EDBT'14. 283--294."},{"key":"e_1_3_2_2_33_1","volume-title":"Proceedings of VLDB'13","volume":"6","author":"Vijayshankar","unstructured":"Vijayshankar Raman et al. 2013. DB2 with BLU acceleration: So much more than just a column store . In Proceedings of VLDB'13 , Vol. , Vol. 6 . VLDB Endowment, 1080--1091. Vijayshankar Raman et al. 2013. DB2 with BLU acceleration: So much more than just a column store. In Proceedings of VLDB'13, Vol., Vol. 6. VLDB Endowment, 1080--1091."},{"key":"e_1_3_2_2_34_1","volume-title":"Proceedings of VLDB'06","author":"Raman Vijayshankar","year":"2006","unstructured":"Vijayshankar Raman and Garret Swart . 2006 . How to wring a table dry: Entropy compression of relations and querying of compressed relations . In Proceedings of VLDB'06 . VLDB Endowment, 858--869. Vijayshankar Raman and Garret Swart. 2006. How to wring a table dry: Entropy compression of relations and querying of compressed relations. In Proceedings of VLDB'06. VLDB Endowment, 858--869."},{"key":"e_1_3_2_2_35_1","volume-title":"Vol.","volume":"29","author":"Rao Jun","year":"2000","unstructured":"Jun Rao and Kenneth A Ross . 2000 . Making B+-trees cache conscious in main memory. In ACM SIGMOD Record , Vol. , Vol. 29 . ACM, 475--486. Jun Rao and Kenneth A Ross. 2000. Making B+-trees cache conscious in main memory. In ACM SIGMOD Record, Vol., Vol. 29. ACM, 475--486."},{"key":"e_1_3_2_2_36_1","volume-title":"Proceedings of VLDB'07","author":"Stonebraker Michael","year":"2007","unstructured":"Michael Stonebraker , Samuel Madden , Daniel J Abadi , Stavros Harizopoulos , Nabil Hachem , and Pat Helland . 2007 . The end of an architectural era:(it's time for a complete rewrite) . In Proceedings of VLDB'07 . VLDB Endowment, 1150--1160. Michael Stonebraker, Samuel Madden, Daniel J Abadi, Stavros Harizopoulos, Nabil Hachem, and Pat Helland. 2007. The end of an architectural era:(it's time for a complete rewrite). In Proceedings of VLDB'07. VLDB Endowment, 1150--1160."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196895"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/355602.361319"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3380583","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3318464.3380583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:52Z","timestamp":1750208512000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3380583"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,31]]},"references-count":40,"alternative-id":["10.1145\/3318464.3380583","10.1145\/3318464"],"URL":"https:\/\/doi.org\/10.1145\/3318464.3380583","relation":{},"subject":[],"published":{"date-parts":[[2020,5,31]]},"assertion":[{"value":"2020-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}