{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:16Z","timestamp":1750308196001,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2004,12,31]],"date-time":"2004-12-31T00:00:00Z","timestamp":1104451200000},"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":[[2004,12,31]]},"abstract":"<jats:p>Ongoing changes in computer architecture are affecting the efficiency of string-sorting algorithms. The size of main memory in typical computers continues to grow but memory accesses require increasing numbers of instruction cycles, which is a problem for the most efficient of the existing string-sorting algorithms as they do not utilize cache well for large data sets. We propose a new sorting algorithm for strings, burstsort, based on dynamic construction of a compact trie in which strings are kept in buckets. It is simple, fast, and efficient. We experimentally explore key implementation options and compare burstsort to existing string-sorting algorithms on large and small sets of strings with a range of characteristics. These experiments show that, for large sets of strings, burstsort is almost twice as fast as any previous algorithm, primarily due to a lower rate of cache miss.<\/jats:p>","DOI":"10.1145\/1005813.1041517","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"source":"Crossref","is-referenced-by-count":24,"title":["Cache-conscious sorting of large sets of strings with dynamic tries"],"prefix":"10.1145","volume":"9","author":[{"given":"Ranjan","family":"Sinha","sequence":"first","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Zobel","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,12,31]]},"reference":[{"volume-title":"IEEE Symposium on the Foundations of Computer Science. IEEE Computer Society","author":"Andersson A.","key":"e_1_2_1_1_1","unstructured":"Andersson , A. and Nilsson , S . 1994. A new efficient radix sort . In IEEE Symposium on the Foundations of Computer Science. IEEE Computer Society , Santa Fe, NM. 714--721. Andersson, A. and Nilsson, S. 1994. A new efficient radix sort. In IEEE Symposium on the Foundations of Computer Science. IEEE Computer Society, Santa Fe, NM. 714--721."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297136"},{"volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM Press, El Paso. 540--548","author":"Arge L.","key":"e_1_2_1_3_1","unstructured":"Arge , L. , Ferragina , P. , Grossi , R. , and Vitter , J. S . 1997. On sorting strings in external memory . In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM Press, El Paso. 540--548 . 10.1145\/258533.258647 Arge, L., Ferragina, P., Grossi, R., and Vitter, J. S. 1997. On sorting strings in external memory. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM Press, El Paso. 540--548. 10.1145\/258533.258647"},{"volume-title":"Proceedings of Annual ACM--SIAM Symposium on Discrete Algorithms. ACM\/SIAM","author":"Bentley J.","key":"e_1_2_1_4_1","unstructured":"Bentley , J. and Sedgewick , R . 1997. Fast algorithms for sorting and searching strings . In Proceedings of Annual ACM--SIAM Symposium on Discrete Algorithms. ACM\/SIAM , New Orleans, LA, 360--369. Bentley, J. and Sedgewick, R. 1997. Fast algorithms for sorting and searching strings. In Proceedings of Annual ACM--SIAM Symposium on Discrete Algorithms. ACM\/SIAM, New Orleans, LA, 360--369."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(94)00047-7"},{"volume-title":"Proceedings of World-Wide Web Conference. Elsevier North-Holland","author":"Hawking D.","key":"e_1_2_1_7_1","unstructured":"Hawking , D. , Craswell , N. , Thistlewaite , P. , and Harman , D . 1999. Results and challenges in web search evaluation . In Proceedings of World-Wide Web Conference. Elsevier North-Holland , Toronto. Hawking, D., Craswell, N., Thistlewaite, P., and Harman, D. 1999. Results and challenges in web search evaluation. In Proceedings of World-Wide Web Conference. Elsevier North-Holland, Toronto."},{"volume-title":"Proceedings of Australasian Computer Science Conference, M. Oudshoorn, Ed. Australian Computer Society","author":"Heinz S.","key":"e_1_2_1_8_1","unstructured":"Heinz , S. and Zobel , J . 2002. Practical data structures for managing small sets of strings . In Proceedings of Australasian Computer Science Conference, M. Oudshoorn, Ed. Australian Computer Society , Melbourne, 75--84. Heinz, S. and Zobel, J. 2002. Practical data structures for managing small sets of strings. In Proceedings of Australasian Computer Science Conference, M. Oudshoorn, Ed. Australian Computer Society, Melbourne, 75--84."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"Hoare C. A. R.","year":"1962","unstructured":"Hoare , C. A. R. 1962 . Quicksort. Comput. J. 5 , 1, 10 -- 15 . Hoare, C. A. R. 1962. Quicksort. Comput. J. 5, 1, 10--15.","journal-title":"Quicksort. Comput. J."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 5th and 6th DIMACS Implementation Challenges, M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, Eds. American Mathematical Society","author":"Johnson D. S.","year":"2002","unstructured":"Johnson , D. S. 2002 . A theoretician's guide to the experimental analysis of algorithms . In Proceedings of the 5th and 6th DIMACS Implementation Challenges, M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, Eds. American Mathematical Society , Providence, RI. Johnson, D. S. 2002. A theoretician's guide to the experimental analysis of algorithms. In Proceedings of the 5th and 6th DIMACS Implementation Challenges, M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, Eds. American Mathematical Society, Providence, RI."},{"volume-title":"Proceedings of Annual ACM--SIAM Symposium on Discrete Algorithms. ACM Press","author":"LaMarca A.","key":"e_1_2_1_12_1","unstructured":"LaMarca , A. and Ladner , R. E . 1997. The influence of caches on the performance of sorting . In Proceedings of Annual ACM--SIAM Symposium on Discrete Algorithms. ACM Press , New Orleans, LA, 370--379. LaMarca, A. and Ladner, R. E. 1997. The influence of caches on the performance of sorting. In Proceedings of Annual ACM--SIAM Symposium on Discrete Algorithms. ACM Press, New Orleans, LA, 370--379."},{"key":"e_1_2_1_13_1","first-page":"5","article-title":"Engineering radix sort","volume":"6","author":"McIlroy P. M.","year":"1993","unstructured":"McIlroy , P. M. , Bostic , K. , and McIlroy , M. D. 1993 . Engineering radix sort . Comput. Syst. 6 , 1, 5 -- 27 . McIlroy, P. M., Bostic, K., and McIlroy, M. D. 1993. Engineering radix sort. Comput. Syst. 6, 1, 5--27.","journal-title":"Comput. Syst."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199607)26:7%3C781::AID-SPE35%3E3.3.CO;2-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384256"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945401"},{"key":"e_1_2_1_18_1","volume-title":"Algorithms in C","author":"Sedgewick R.","unstructured":"Sedgewick , R. 1998. Algorithms in C , 3 rd ed. Addison-Wesley Longman , Reading, MA . Sedgewick, R. 1998. Algorithms in C, 3rd ed. Addison-Wesley Longman, Reading, MA.","edition":"3"},{"key":"e_1_2_1_19_1","unstructured":"Seward J. 2001. Valgrind---memory and cache profiler. http:\/\/developer.kde.org\/&sim;sewardj\/docs-1.9.5\/cg_techdocs.html.  Seward J. 2001. Valgrind---memory and cache profiler. http:\/\/developer.kde.org\/&sim;sewardj\/docs-1.9.5\/cg_techdocs.html."},{"volume-title":"School of Computer Science and Information Technology","author":"Sinha R.","key":"e_1_2_1_20_1","unstructured":"Sinha , R. 2002. Fast sorting of strings with dynamic tries. Minor Thesis , School of Computer Science and Information Technology , RMIT University . Sinha, R. 2002. Fast sorting of strings with dynamic tries. Minor Thesis, School of Computer Science and Information Technology, RMIT University."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384245"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005813.1041517","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1005813.1041517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:24:55Z","timestamp":1750263895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005813.1041517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,31]]},"references-count":20,"alternative-id":["10.1145\/1005813.1041517"],"URL":"https:\/\/doi.org\/10.1145\/1005813.1041517","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2004,12,31]]}}}