Cache-conscious sorting of large sets of strings with dynamic tries

Sinha, R and Zobel, J 2004, 'Cache-conscious sorting of large sets of strings with dynamic tries', Journal of Experimental Algorithmics, vol. 9, pp. 1-31.


Document type: Journal Article
Collection: Journal Articles

Title Cache-conscious sorting of large sets of strings with dynamic tries
Author(s) Sinha, R
Zobel, J
Year 2004
Journal name Journal of Experimental Algorithmics
Volume number 9
Start page 1
End page 31
Total pages 30
Publisher Association for Computing Machinery
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.
Subject Information Systems Management
Copyright notice © 2004 ACM
ISSN 1084-6654
Versions
Version Filter Type
Access Statistics: 214 Abstract Views  -  Detailed Statistics
Created: Wed, 18 Feb 2009, 09:53:18 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us