.png){kind=icon}
.png){kind=icon}
Return
Tunnel: Parallel-inducing sort for large string analytics
.png){kind=icon}
OA
AI
DOI：10.1016/j.future.2023.08.009.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The suffix array is a crucial data structure for efficient string analysis. Over the course of twenty-six years, sequential suffix array construction algorithms have achieved O(n) time complexity and inplace sorting. In this paper, we present the Tunnel algorithm, the first large-scale parallel suffix array (n ) construction algorithm with a time complexity of O based on the parallel random access machine (PRAM) model. The Tunnel algorithm is built on three key ideas: dividing the problem of size O(n) into p sub-problems of reduced size O by replacing long suffixes with shorter prefixes of size at most a constant D; introducing a Tunnel mechanism to efficiently induce the order of a set of suffixes with long common prefixes; developing a strategy to transform a partially ordered suffix set into a total order relation by iteratively applying the Tunnel inducing method. We provide a detailed description of the algorithm, along with a thorough analysis of its time and space complexity, to demonstrate its correctness and efficiency. The proposed Tunnel algorithm exhibits scalable performance, making it suitable for large string analytics on large-scale parallel systems. & COPY; 2023 Elsevier B.V. All rights reserved.
Keywords:
Suffix array
String algorithm
Parallel sorting
String analysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
F
IF:
6.1
Papers:
6.8K
Citations:
2.3W