Loading...
Please wait, while we are loading the content...
Similar Documents
Cache-conscious sorting of large sets of strings with dynamic tries
| Content Provider | ACM Digital Library |
|---|---|
| Author | Sinha, Ranjan Zobel, Justin |
| Copyright Year | 2004 |
| Abstract | 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. |
| File Format | |
| ISSN | 10846654 |
| e-ISSN | 10846654 |
| DOI | 10.1145/1005813.1041517 |
| Journal | Journal of Experimental Algorithmics (JEA) |
| Volume Number | 9 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2004-12-01 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Content Type | Text |
| Resource Type | Article |
| Subject | Theoretical Computer Science |
