期刊
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
卷 149, 期 -, 页码 650-663出版社
ELSEVIER
DOI: 10.1016/j.future.2023.08.009
关键词
Suffix array; String algorithm; Parallel sorting; String analysis
This paper presents the Tunnel algorithm, the first large-scale parallel suffix array construction algorithm with a time complexity of O based on the PRAM model. The algorithm divides the problem into sub-problems, efficiently induces the order of suffixes with long common prefixes, and transforms a partially ordered suffix set into a total order relation. The Tunnel algorithm is scalable and suitable for large string analytics on parallel systems.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据