Fast in-place suffix sorting on a multicore computer

Bin LAO, Ge NONG, Wai Hong CHAN, Jing Yi XIE

Research output: Contribution to journalArticles

2 Citations (Scopus)

Abstract

Sorting all suffixes of an input string X will produce the suffix array that is a fundamental data structure for full-text search on X. To utilize the parallel computing power of a multicore machine with shared memory, this article designs a fast linear-time and in-place parallel algorithm called pSACAK, for sorting the suffixes of an input string with a constant alphabet. This algorithm is a parallel variant of the sequential suffix sorting algorithm SACAK which improved the linear-time SAIS to be in-place for constant alphabets, and hence requires only a workspace of O(K) for alphabet size K. While our recent work has successfully designed the parallel variant of SAIS on a multicore machine, it remains a challenge to parallelize SACAK due to the strong data dependencies caused by the in-place constraint. A number of new techniques are proposed here to overcome the difficulties for designing pSACAK from the sequential SACAK. An experimental study is conducted to evaluate the performance of pSACAK versus other existing parallel suffix sorting algorithms. Our experimental results show that pSACAK is the most time and space efficient among all in comparison. To the best of our knowledge, pSACAK is the only linear-time and in-place parallel suffix sorting algorithm for constant alphabets reported so far. Copyright © 2018 IEEE.
Original languageEnglish
Pages (from-to)1737-1749
JournalIEEE Transactions on Computers
Volume67
Issue number12
Early online dateJun 2018
DOIs
Publication statusPublished - Dec 2018

Citation

Lao, B., Nong, G., Chan, W. H., & Xie, J. Y. (2018). Fast in-place suffix sorting on a multicore computer. IEEE Transactions on Computers, 67(12), 1737-1749. doi: 10.1109/TC.2018.2842050

Keywords

  • Suffix sorting
  • Parallel algorithm
  • Linear-time
  • In-place

Fingerprint Dive into the research topics of 'Fast in-place suffix sorting on a multicore computer'. Together they form a unique fingerprint.