Efficient String Sorting Algorithms: Cache-aware and Cache-Oblivious
R. Angrish, Deepak Garg · 2011
Abstract— Sorting is a process of rearranging a sequence of objects into some kind of predefined linear order. String data is very common and most occurring data type. Sorting a string involves comparison it character by character which is more time consuming than integer sorting. Also, sorting forms the basis of many applications like data processing, databases, pattern matching and searching etc. So implementing improvements to make it fast and efficient will help in reducing the computational time and thus making our applications run faster. This paper briefs about various fast and efficient string sorting algorithms. The algorithms have been divided into two categories: cache-aware and cache-oblivious. The various algorithms discussed are: CRadix Sort, Burstsort and cache- oblivious string sorting algorithm. The improvement in CRadix Sort is achieved by starting the sorting with the most significant digit and associating a small block of main memory called the key buffer to each key and sorting a portion of each key into its corresponding key buffer. Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted in cache. The cache- oblivious string sorting algorithm is a randomized algorithm for string sorting which uses signature technique (reduces the sequence by creating a set of signatures strings having the same trie structure as the original set) to sort strings. comparison is done character by character unlike integer sorting in which the entire key is compared at once and also string lengths are variable and swapping them is more difficult. Now-a-days manipulation of large data sets is a common thing in every area of application like databases, digital libraries, etc. The size of data sets have increased to such an extent that they now do not fit into the internal memory of the computer systems thus they need to be stored in external memory devices or secondary storages like CD, disks, etc., thus increasing the latency time as the external memories are slower than the cache memory. If the problem set is very large the latency time dominates the overall execution time thereby increasing the computation time. The difference in speeds of the memories is increasing rapidly with increasing technology thus leading to increase in latency time i.e., increasing I/O bottleneck making the situation worse (12). The performance of traditional string sorting algorithms degrades when the problem set does not fit into internal memory. This paper discusses various algorithms that aim at minimizing the number of cache misses so that the I/O bottleneck problem can be reduced thus making it more efficient and fast..