Parallel Suffix Sorting for Large String Analytics

Zhihui Du; Sen Zhang; David A. Bader

doi:10.1007/978-3-031-30442-2_6

Parallel Suffix Sorting for Large String Analytics

Zhihui Du, Sen Zhang, David A. Bader

Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential suffix array construction algorithm to achieve O(n) time complexity and in-place sorting. In this paper, we develop the D-Limited Parallel Induce (DLPI) algorithm, the first O(np) time parallel suffix array construction algorithm. The basic idea of DLPI includes two aspects: dividing the O(n) size problem into p reduced sub-problems with size O(np) so we can handle them on p processors in parallel; developing an efficient parallel induce sorting method to achieve correct order for all the reduced sub-problems. The complete algorithm description is given to show the implementation method of the proposed idea. The time and space complexity analysis and proof are also given to show the correctness and efficiency of the proposed algorithm. The proposed DLPI algorithm can handle large strings with scalable performance.

Original language	English (US)
Title of host publication	Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers
Editors	Roman Wyrzykowski, Jack Dongarra, Ewa Deelman, Konrad Karczewski
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	71-82
Number of pages	12
ISBN (Print)	9783031304415
DOIs	https://doi.org/10.1007/978-3-031-30442-2_6
State	Published - 2023
Event	14th International Conference on Parallel Processing and Applied Mathematics, PPAM 2022 - Gdansk, Poland Duration: Sep 11 2022 → Sep 14 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13826 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Parallel Processing and Applied Mathematics, PPAM 2022
Country/Territory	Poland
City	Gdansk
Period	9/11/22 → 9/14/22

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Optimal Algorithm
Parallel Sorting
String Algorithm
String Analysis
Suffix Array

Access to Document

10.1007/978-3-031-30442-2_6

Cite this

Du, Z., Zhang, S., & Bader, D. A. (2023). Parallel Suffix Sorting for Large String Analytics. In R. Wyrzykowski, J. Dongarra, E. Deelman, & K. Karczewski (Eds.), Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers (pp. 71-82). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13826 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-30442-2_6

Du, Zhihui ; Zhang, Sen ; Bader, David A. / Parallel Suffix Sorting for Large String Analytics. Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers. editor / Roman Wyrzykowski ; Jack Dongarra ; Ewa Deelman ; Konrad Karczewski. Springer Science and Business Media Deutschland GmbH, 2023. pp. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c29cb77656724429814b98c7f7bfd4c8,

title = "Parallel Suffix Sorting for Large String Analytics",

abstract = "The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential suffix array construction algorithm to achieve O(n) time complexity and in-place sorting. In this paper, we develop the D-Limited Parallel Induce (DLPI) algorithm, the first O(np) time parallel suffix array construction algorithm. The basic idea of DLPI includes two aspects: dividing the O(n) size problem into p reduced sub-problems with size O(np) so we can handle them on p processors in parallel; developing an efficient parallel induce sorting method to achieve correct order for all the reduced sub-problems. The complete algorithm description is given to show the implementation method of the proposed idea. The time and space complexity analysis and proof are also given to show the correctness and efficiency of the proposed algorithm. The proposed DLPI algorithm can handle large strings with scalable performance.",

keywords = "Optimal Algorithm, Parallel Sorting, String Algorithm, String Analysis, Suffix Array",

author = "Zhihui Du and Sen Zhang and Bader, {David A.}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 14th International Conference on Parallel Processing and Applied Mathematics, PPAM 2022 ; Conference date: 11-09-2022 Through 14-09-2022",

year = "2023",

doi = "10.1007/978-3-031-30442-2_6",

language = "English (US)",

isbn = "9783031304415",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "71--82",

editor = "Roman Wyrzykowski and Jack Dongarra and Ewa Deelman and Konrad Karczewski",

booktitle = "Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers",

address = "Germany",

}

Du, Z, Zhang, S & Bader, DA 2023, Parallel Suffix Sorting for Large String Analytics. in R Wyrzykowski, J Dongarra, E Deelman & K Karczewski (eds), Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13826 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 71-82, 14th International Conference on Parallel Processing and Applied Mathematics, PPAM 2022, Gdansk, Poland, 9/11/22. https://doi.org/10.1007/978-3-031-30442-2_6

Parallel Suffix Sorting for Large String Analytics. / Du, Zhihui; Zhang, Sen; Bader, David A.
Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers. ed. / Roman Wyrzykowski; Jack Dongarra; Ewa Deelman; Konrad Karczewski. Springer Science and Business Media Deutschland GmbH, 2023. p. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13826 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Parallel Suffix Sorting for Large String Analytics

AU - Du, Zhihui

AU - Zhang, Sen

AU - Bader, David A.

PY - 2023

Y1 - 2023

N2 - The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential suffix array construction algorithm to achieve O(n) time complexity and in-place sorting. In this paper, we develop the D-Limited Parallel Induce (DLPI) algorithm, the first O(np) time parallel suffix array construction algorithm. The basic idea of DLPI includes two aspects: dividing the O(n) size problem into p reduced sub-problems with size O(np) so we can handle them on p processors in parallel; developing an efficient parallel induce sorting method to achieve correct order for all the reduced sub-problems. The complete algorithm description is given to show the implementation method of the proposed idea. The time and space complexity analysis and proof are also given to show the correctness and efficiency of the proposed algorithm. The proposed DLPI algorithm can handle large strings with scalable performance.

AB - The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential suffix array construction algorithm to achieve O(n) time complexity and in-place sorting. In this paper, we develop the D-Limited Parallel Induce (DLPI) algorithm, the first O(np) time parallel suffix array construction algorithm. The basic idea of DLPI includes two aspects: dividing the O(n) size problem into p reduced sub-problems with size O(np) so we can handle them on p processors in parallel; developing an efficient parallel induce sorting method to achieve correct order for all the reduced sub-problems. The complete algorithm description is given to show the implementation method of the proposed idea. The time and space complexity analysis and proof are also given to show the correctness and efficiency of the proposed algorithm. The proposed DLPI algorithm can handle large strings with scalable performance.

KW - Optimal Algorithm

KW - Parallel Sorting

KW - String Algorithm

KW - String Analysis

KW - Suffix Array

UR - http://www.scopus.com/inward/record.url?scp=85161428178&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85161428178&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-30442-2_6

DO - 10.1007/978-3-031-30442-2_6

M3 - Conference contribution

AN - SCOPUS:85161428178

SN - 9783031304415

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 82

BT - Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers

A2 - Wyrzykowski, Roman

A2 - Dongarra, Jack

A2 - Deelman, Ewa

A2 - Karczewski, Konrad

PB - Springer Science and Business Media Deutschland GmbH

T2 - 14th International Conference on Parallel Processing and Applied Mathematics, PPAM 2022

Y2 - 11 September 2022 through 14 September 2022

ER -

Du Z, Zhang S, Bader DA. Parallel Suffix Sorting for Large String Analytics. In Wyrzykowski R, Dongarra J, Deelman E, Karczewski K, editors, Parallel Processing and Applied Mathematics - 14th International Conference, PPAM 2022, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2023. p. 71-82. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-30442-2_6