Using compact tries for cache-efficient sorting of integers

Sinha, R 2004, 'Using compact tries for cache-efficient sorting of integers', in C. Ribeiro and S. Martins (ed.) Experimental and Efficient Algorithms: Third International Workshop, WEA 2004, Angra dos Reis, Brazil, 20 April 2004, pp. 513-528.


Document type: Conference Paper
Collection: Conference Papers

Title Using compact tries for cache-efficient sorting of integers
Author(s) Sinha, R
Year 2004
Conference name International Workshop on Experimental and Efficient Algorithms
Conference location Angra dos Reis, Brazil
Conference dates 20 April 2004
Proceedings title Experimental and Efficient Algorithms: Third International Workshop, WEA 2004
Editor(s) C. Ribeiro
S. Martins
Publisher Springer
Place of publication Berlin, Germany
Start page 513
End page 528
Total pages 16
Abstract The increasing latency between memory and processor speeds has made it imperative for algorithms to reduce expensive accesses to main memory. In earlier work, we presented cache-conscious algorithms for sorting strings, that have been shown to be almost two times faster than the previous algorithms, mainly due to better usage of the cache. In this paper, we propose two new algorithms, Burstsort and MEBurstsort, for sorting large sets of integer keys. Our algorithms use a novel approach for sorting integers, by dynamically constructing a compact trie which is used to allocate the keys to containers. These keys are then sorted within the cache. The new algorithms are simple, fast and efficient. We compare them against the best existing algorithms using several collections and data sizes. Our results show that MEBurstsort is up to 3.5 times faster than memory-tuned quicksort for 64-bit keys and up to 2.5 times faster for 32-bit keys. For 32-bit keys, on 10 of the 11 collections used, MEBurstsort was the fastest, whereas for 64-bit keys, it was the fastest for all collections.
Subjects Information Systems Management
Keyword(s) efficiency
sorting
sorting integer keys
DOI - identifier 10.1007/b97914
Copyright notice © Springer-Verlag Berlin Heidelberg 2004
ISBN 978-3-540-22067-1
Versions
Version Filter Type
Altmetric details:
Access Statistics: 238 Abstract Views  -  Detailed Statistics
Created: Wed, 08 Apr 2009, 09:42:32 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us