{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:57Z","timestamp":1773481797680,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>We present the Height Optimized Trie (HOT), a fast and space-efficient in-memory index structure. The core algorithmic idea of HOT is to dynamically vary the number of bits considered at each node, which enables a consistently high fanout and thereby good cache efficiency. For a fixed maximum node fanout, the overall tree height is minimal and its structure is deterministically defined. Multiple carefully engineered node implementations using SIMD instructions or lightweight compression schemes provide compactness and fast search and optimize HOT structures for different usage scenarios. Our experiments, which use a wide variety of workloads and data sets, show that HOT outperforms other state-of-the-art index structures for string keys both in terms of search performance and memory footprint, while being competitive for integer keys.<\/jats:p>","DOI":"10.1145\/3506692","type":"journal-article","created":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T12:27:52Z","timestamp":1649248072000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Height Optimized Tries"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1062-8419","authenticated-orcid":false,"given":"Robert","family":"Binna","sequence":"first","affiliation":[{"name":"University of Innsbruck, Innsbruck, Austria"}]},{"given":"Eva","family":"Zangerle","sequence":"additional","affiliation":[{"name":"University of Innsbruck, Innsbruck, Austria"}]},{"given":"Martin","family":"Pichl","sequence":"additional","affiliation":[{"name":"University of Innsbruck, Innsbruck, Austria"}]},{"given":"G\u00fcnther","family":"Specht","sequence":"additional","affiliation":[{"name":"University of Innsbruck, Innsbruck, Austria"}]},{"given":"Viktor","family":"Leis","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,4,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90068-K"},{"key":"e_1_3_2_3_2","first-page":"97","article-title":"HAT-trie: A cache-conscious trie-based data structure for strings","author":"Askitis Nikolas","year":"2007","unstructured":"Nikolas Askitis and Ranjan Sinha. 2007. HAT-trie: A cache-conscious trie-based data structure for strings. Proceedings of the 30th Australasian Conference on Computer Science. 97\u2013105. Retrieved from http:\/\/crpit.scem.westernsydney.edu.au\/abstracts\/CRPITV62Askitis.html.","journal-title":"Proceedings of the 30th Australasian Conference on Computer Science"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76298-0_52"},{"key":"e_1_3_2_5_2","volume-title":"STX B+ Tree C++ Template Classes","author":"Bingmann Timo","year":"2008","unstructured":"Timo Bingmann. 2008. STX B+ Tree C++ Template Classes. Retrieved from http:\/\/panthema.net\/2007\/stx-btree."},{"key":"e_1_3_2_6_2","first-page":"30","volume-title":"Proceedings of the 2nd International Workshop on In Memory Data Management and Analytics, IMDM 2014","author":"Binna Robert","year":"2014","unstructured":"Robert Binna, Dominic Pacher, Thomas Meindl, and G\u00fcnther Specht. 2014. The DCB-tree: A space-efficient delta coded cache conscious B-tree. In Proceedings of the 2nd International Workshop on In Memory Data Management and Analytics, IMDM 2014. 30\u201341. Retrieved from http:\/\/www-db.in.tum.de\/hosted\/imdm2014\/papers\/binna.pdf."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_3_2_8_2","volume-title":"Fast and Space-Efficient Indexing For Main-Memory Database Systems on Modern Hardware","author":"Robert Binna,","year":"2020","unstructured":"Binna, Robert. 2020. Fast and Space-Efficient Indexing For Main-Memory Database Systems on Modern Hardware. Ph. D. Dissertation. University of Innsbruck, Austria. Retrieved from https:\/\/diglib.uibk.ac.at\/ulbtirolhs\/content\/titleinfo\/5124193\/full.pdf."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559877"},{"key":"e_1_3_2_10_2","first-page":"227","volume-title":"Proceedings of the 14th BTW Conference on Database Systems for Business, Technology, and Web","author":"B\u00f6hm Matthias","year":"2011","unstructured":"Matthias B\u00f6hm, Benjamin Schlegel, Peter Benjamin Volk, Ulrike Fischer, Dirk Habich, and Wolfgang Lehner. 2011. Efficient in-memory indexing with generalized prefix trees. In Proceedings of the 14th BTW Conference on Database Systems for Business, Technology, and Web. 227\u2013246. Retrieved from http:\/\/subs.emis.de\/LNI\/Proceedings\/Proceedings180\/article22.html."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375688"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/129888.129896"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806908"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914847"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.04.010"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963192.1963296"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454211"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767867"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746480"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2236584.2236587"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.004"},{"issue":"1","key":"e_1_3_2_25_2","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\u201384.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809990"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_3_2_32_2","first-page":"25","volume-title":"Proceedings of the 2nd International Workshop on Algorithm Engineering (WAE\u201998)","author":"Nilsson Stefan","year":"1998","unstructured":"Stefan Nilsson and Matti Tikkanen. 1998. Implementing a dynamic compressed trie. In Proceedings of the 2nd International Workshop on Algorithm Engineering (WAE\u201998). 25\u201336."},{"key":"e_1_3_2_33_2","first-page":"475","volume-title":"VLDB\u201999, Proceedings of 25th International Conference on Very Large Data Bases","author":"Rao Jun","year":"1999","unstructured":"Jun Rao and Kenneth A. Ross. 1999. Cache conscious indexing for decision-support in main memory. In VLDB\u201999, Proceedings of 25th International Conference on Very Large Data Bases. 475\u2013486. Retrieved from http:\/\/www.vldb.org\/conf\/1999\/P7.pdf."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1565694.1565705"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196895"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.54"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2014.10"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375660"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3506692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3506692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:50Z","timestamp":1750191110000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3506692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3506692"],"URL":"https:\/\/doi.org\/10.1145\/3506692","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,31]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}