{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T06:51:19Z","timestamp":1672296679516},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2005,12,31]]},"abstract":"<jats:p>Algorithms for sorting large datasets can be made more efficient with careful use of memory hierarchies and reduction in the number of costly memory accesses. In earlier work, we introduced burstsort, a new string-sorting algorithm that on large sets of strings is almost twice as fast as previous algorithms, primarily because it is more cache efficient. Burstsort dynamically builds a small trie that is used to rapidly allocate each string to a bucket. In this paper, we introduce new variants of our algorithm: SR-burstsort, DR-burstsort, and DRL-burstsort. These algorithms use a random sample of the strings to construct an approximation to the trie prior to sorting. Our experimental results with sets of over 30 million strings show that the new variants reduce, by up to 37%, cache misses further than did the original burstsort, while simultaneously reducing instruction counts by up to 24%. In pathological cases, even further savings can be obtained.<\/jats:p>","DOI":"10.1145\/1064546.1180622","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":4,"title":["Using random sampling to build approximate tries for efficient string sorting"],"prefix":"10.1145","volume":"10","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":[[2005,12,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA.   Aho A. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297136"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258647"},{"key":"e_1_2_1_4_1","volume-title":"Proc. Annual ACM-SIAM Symp. on Discrete Algorithms, M. Saks, 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, M. Saks, 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, M. Saks, Ed. Society for Industrial and Applied Mathematics, New Orleans, LA. 360--369."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90028-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/174666.174667"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(94)00047-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00024-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_10_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 , San Mateo, CA . Hennessy, J. L. and Patterson, D. A. 2002. Computer Architecture: A Quantitative Approach, 3rd ed. Morgan Kaufmann, San Mateo, CA.","edition":"3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0985"},{"key":"e_1_2_1_12_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"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Random sampling from databases---a survey","volume":"5","author":"Olken F.","year":"1995","unstructured":"Olken , F. and Rotem , D. 1995 . Random sampling from databases---a survey . Statistics and Computing 5 , 1 (Mar.), 25--42. Olken, F. and Rotem, D. 1995. Random sampling from databases---a survey. Statistics and Computing 5, 1 (Mar.), 25--42.","journal-title":"Statistics and Computing"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945401"},{"key":"e_1_2_1_17_1","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","doi-asserted-by":"publisher","DOI":"10.1145\/1005813.1041517"},{"key":"e_1_2_1_19_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\/pdf\/10.1145\/1064546.1180622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:10:28Z","timestamp":1672229428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1064546.1180622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,31]]},"references-count":18,"alternative-id":["10.1145\/1064546.1180622"],"URL":"https:\/\/doi.org\/10.1145\/1064546.1180622","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,31]]}}}