{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:32Z","timestamp":1750308812624,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            In this article, we experimentally compare a number of data structures operating over keys that are 32- and 64-bit integers. We examine traditional comparison-based search trees as well as data structures that take advantage of the fact that the keys are integers such as van Emde Boas trees and various trie-based data structures. We propose a variant of a burst trie that performs better in time than all the alternative data structures. In addition, even for small sets of keys, this burst trie variant occupies less space than comparison-based data structures such as red-black trees and\n            <jats:italic>B<\/jats:italic>\n            -trees. Burst tries have previously been shown to provide a very efficient base for implementing cache efficient string sorting algorithms. We find that with suitable engineering, they also perform excellently as a dynamic ordered data structure operating over integer keys. We provide experimental results when the data structures operate over uniform random data. We also present experimental results for other types of data, including datasets arising from\n            <jats:italic>Valgrind<\/jats:italic>\n            , a widely used suite of tools for the dynamic binary instrumentation of programs.\n          <\/jats:p>","DOI":"10.1145\/1671970.1671977","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":0,"title":["Comparing integer data structures for 32- and 64-bit keys"],"prefix":"10.1145","volume":"15","author":[{"given":"Nicholas","family":"Nash","sequence":"first","affiliation":[{"name":"Trinity College Dublin, Ireland"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Lero, Trinity College Dublin, Ireland"}]}],"member":"320","published-online":{"date-parts":[[2010,3,17]]},"reference":[{"volume-title":"Proceedings of the 1st International Workshop on Algorithm Engineering and Experimentation (ALENEX'99)","author":"Acharya A.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90068-K"},{"volume-title":"Proceedings of the 32nd Australasian Computer Science Conference (ACSC'09)","year":"2009","author":"Askitis N.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","first-page":"173","article-title":"Organization and maintenance of large ordered indices. Acta","volume":"1","author":"Bayer R.","year":"1972","journal-title":"Inf."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796541"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v011.i05"},{"volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02)","author":"Brodal G. S.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. MIT Press Cambridge MA 273--301.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. MIT Press Cambridge MA 273--301."},{"key":"e_1_2_1_9_1","unstructured":"Crosbie R. and Gregg D. 2009. Searching the parameter space for burst tries.  Crosbie R. and Gregg D. 2009. Searching the parameter space for burst tries."},{"key":"e_1_2_1_10_1","first-page":"897","article-title":"Fixed universe successor problem","volume":"6","author":"Demaine E.","year":"2003","journal-title":"Advanced Data Structures, MIT Course"},{"volume-title":"Proceedings of the 6th SIAM Workshop on Algorithm Engineering and Experiments. SIAM","author":"Dementiev R.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1370602"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1564505"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"Standard for floating-point arithmetic","volume":"754","author":"IEEE.","year":"2008","journal-title":"IEEE Std"},{"key":"e_1_2_1_17_1","unstructured":"Intel. 2007. Intel 64 and IA-32 Architectures Optimization Reference Manual.  Intel. 2007. Intel 64 and IA-32 Architectures Optimization Reference Manual."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290681"},{"volume-title":"Department of Electrical Engineering and Computer Science","author":"Kasheff Z.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690333"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Knessl C. and Szpankowski W. 2000b. A note on the asymptotic behavior of the heights in b-tries for b large. Electr. J. Comb. 7.  Knessl C. and Szpankowski W. 2000b. A note on the asymptotic behavior of the heights in b-tries for b large. Electr. J. Comb. 7.","DOI":"10.37236\/1517"},{"edition":"2","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth D. E.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE'99)","author":"Korda M.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","unstructured":"Manegold S. and Boncz P. 2004. Cache-memory and tlb calibration tool. http:\/\/homepages.cwi.nl\/~manegold\/Calibrator\/calibrator.shtml  Manegold S. and Boncz P. 2004. Cache-memory and tlb calibration tool. http:\/\/homepages.cwi.nl\/~manegold\/Calibrator\/calibrator.shtml"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90022-P"},{"volume-title":"Proceedings of the 7th International Workshop on Experimental Algorithms. Springer","author":"Nash N.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0102-y"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335449"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24838-5_38"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1187439"},{"volume-title":"Proceedings of the 7th International Workshop on Efficient and Experimental Algorithms (WEA'08)","author":"Sinha R.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005813.1041517"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064546.1180622"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"edition":"3","volume-title":"The C++ Programming Language","author":"Stroustrup B.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/366552.366600"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90020-5"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1671970.1671977","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1671970.1671977","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:24Z","timestamp":1750278384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1671970.1671977"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":38,"alternative-id":["10.1145\/1671970.1671977"],"URL":"https:\/\/doi.org\/10.1145\/1671970.1671977","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}