Conference Proceedings

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

R Sinha, J Zobel, R Ladner (ed.)

PROCEEDINGS OF THE FIFTH WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENT | SIAM | Published : 2003

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 ..

View full abstract

University of Melbourne Researchers