{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:41:50Z","timestamp":1750308110682,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"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":[[2007,2,9]]},"abstract":"<jats:p>Burstsort is a cache-oriented sorting technique that uses a dynamic trie to efficiently divide large sets of string keys into related subsets small enough to sort in cache. In our original burstsort, string keys sharing a common prefix were managed via a bucket of pointers represented as a list or array; this approach was found to be up to twice as fast as the previous best string sorts, mostly because of a sharp reduction in out-of-cache references. In this paper, we introduce C-burstsort, which copies the unexamined tail of each key to the bucket and discards the original key to improve data locality. On both Intel and PowerPC architectures, and on a wide range of string types, we show that sorting is typically twice as fast as our original burstsort and four to five times faster than multikey quicksort and previous radixsorts. A variant that copies both suffixes and record pointers to buckets, CP-burstsort, uses more memory, but provides stable sorting. In current computers, where performance is limited by memory access latencies, these new algorithms can dramatically reduce the time needed for internal sorting of large numbers of strings.<\/jats:p>","DOI":"10.1145\/1187436.1187439","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"source":"Crossref","is-referenced-by-count":17,"title":["Cache-efficient string sorting using copying"],"prefix":"10.1145","volume":"11","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"}]},{"given":"David","family":"Ring","sequence":"additional","affiliation":[{"name":"Palo Alto, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/297096.297136"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"2963","DOI":"10.1093\/nar\/21.13.2963","article-title":"Genbank","volume":"21","author":"Benson D.","year":"1993","unstructured":"Benson , D. , Lipman , D. J. , and Ostell , J. 1993 . Genbank . Nucleic Acids Research 21 , 13, 2963 -- 2965 . Benson, D., Lipman, D. J., and Ostell, J. 1993. Genbank. Nucleic Acids Research 21, 13, 2963--2965.","journal-title":"Nucleic Acids Research"},{"volume-title":"Proc. Annual ACM-SIAM Symp. on Discrete Algorithms, Ed. Society for Industrial and Applied Mathematics","author":"Bentley J.","unstructured":"Bentley , J. and Sedgewick , R . 1997. Fast algorithms for sorting and searching strings . In Proc. Annual ACM-SIAM Symp. on Discrete Algorithms, Ed. Society for Industrial and Applied Mathematics , New Orleans, LA. 360--369. Bentley, J. and Sedgewick, R. 1997. Fast algorithms for sorting and searching strings. In Proc. Annual ACM-SIAM Symp. on Discrete Algorithms, Ed. Society for Industrial and Applied Mathematics, New Orleans, LA. 360--369.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1002\/spe.4380231105"},{"volume-title":"Proc. Conf. on Linux Clusters: The HPC Revolution","author":"Dongarra J.","unstructured":"Dongarra , J. , London , K. , Moore , S. , Mucci , S. , and Terpstra , D . 2001. Using PAPI for hardware performance monitoring on linux systems . In Proc. Conf. on Linux Clusters: The HPC Revolution . Urbana, Illinois. Dongarra, J., London, K., Moore, S., Mucci, S., and Terpstra, D. 2001. Using PAPI for hardware performance monitoring on linux systems. In Proc. Conf. on Linux Clusters: The HPC Revolution. Urbana, Illinois.","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/0306-4573(94)00047-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/S1389-1286(99)00024-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_9_1","volume-title":"Computer Architecture: A Quantitative Approach","author":"Hennessy J. L.","year":"2002","unstructured":"Hennessy , J. L. and Patterson , D. A . 2002 . Computer Architecture: A Quantitative Approach , 3 rd Ed. Morgan Kaufmann Publishers , San Mateo, CA . Hennessy, J. L. and Patterson, D. A. 2002. Computer Architecture: A Quantitative Approach, 3rd Ed. Morgan Kaufmann Publishers, San Mateo, CA.","edition":"3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/366622.366644"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","article-title":"Quicksort","volume":"5","author":"Hoare C. A. R.","year":"1962","unstructured":"Hoare , C. A. R. 1962 . Quicksort . Computer Jour. 5 , 1, 10 -- 15 . Hoare, C. A. R. 1962. Quicksort. Computer Jour. 5, 1, 10--15.","journal-title":"Computer Jour."},{"volume-title":"Proc. Euromicro Workshop on Parallel, Distributed and Network-based Processing, A. Clematis, Ed. IEEE Computer Society Press","author":"Jimenez-Gonzalez D.","unstructured":"Jimenez-Gonzalez , D. , Navarro , J. , and Larriba-Pey , J. L . 2003. CC-radix: a cache conscious sorting based on radix sort . In Proc. Euromicro Workshop on Parallel, Distributed and Network-based Processing, A. Clematis, Ed. IEEE Computer Society Press , Los Alamitos, CA, USA, 101--108. Jimenez-Gonzalez, D., Navarro, J., and Larriba-Pey, J. L. 2003. CC-radix: a cache conscious sorting based on radix sort. In Proc. Euromicro Workshop on Parallel, Distributed and Network-based Processing, A. Clematis, Ed. IEEE Computer Society Press, Los Alamitos, CA, USA, 101--108.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1006\/jagm.1998.0985"},{"key":"e_1_2_1_14_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 . Computing Systems 6 , 1, 5 -- 27 . McIlroy, P. M., Bostic, K., and McIlroy, M. D. 1993. Engineering radix sort. Computing Systems 6, 1, 5--27.","journal-title":"Computing Systems"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/351827.384256"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/945394.945401"},{"unstructured":"Seward J. 2001. Valgrind---memory and cache profiler. http:\/\/developer.kde.org\/~sewardj\/docs-1.9.5\/cg_techdocs.html.  Seward J. 2001. Valgrind---memory and cache profiler. http:\/\/developer.kde.org\/~sewardj\/docs-1.9.5\/cg_techdocs.html.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","volume-title":"Proc. International Workshop on Efficient and Experimental Algorithms, C. C. Ribeiro, Ed. Lecture Notes in Computer Science","volume":"3059","author":"Sinha R.","year":"2004","unstructured":"Sinha , R. 2004 . Using compact tries for cache-efficient sorting of integers . In Proc. International Workshop on Efficient and Experimental Algorithms, C. C. Ribeiro, Ed. Lecture Notes in Computer Science , vol. 3059 . Springer-Verlag, New York. 513--528. Sinha, R. 2004. Using compact tries for cache-efficient sorting of integers. In Proc. International Workshop on Efficient and Experimental Algorithms, C. C. Ribeiro, Ed. Lecture Notes in Computer Science, vol. 3059. Springer-Verlag, New York. 513--528."},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1005813.1041517"},{"key":"e_1_2_1_21_1","volume-title":"Proc. International Workshop on Efficient and Experimental Algorithms, C. C. Ribeiro, Ed. Lecture Notes in Computer Science","volume":"3059","author":"Sinha R.","unstructured":"Sinha , R. and Zobel , J . 2004b. Using random sampling to build approximate tries for efficient string sorting . In Proc. International Workshop on Efficient and Experimental Algorithms, C. C. Ribeiro, Ed. Lecture Notes in Computer Science , vol. 3059 . Springer-Verlag, New York. 529--544. Sinha, R. and Zobel, J. 2004b. Using random sampling to build approximate tries for efficient string sorting. In Proc. International Workshop on Efficient and Experimental Algorithms, C. C. Ribeiro, Ed. Lecture Notes in Computer Science, vol. 3059. Springer-Verlag, New York. 529--544."},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/944618.944627"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","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\/1187436.1187439","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1187439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1187439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":22,"alternative-id":["10.1145\/1187436.1187439"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1187439","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}