2015/09/21 by Matevž Jekovec, Jekovec, Matevž, Andrej Brodnik +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1509.06167
openalex publication_date 2015/09/21 · arxiv created 2015/09/29 · arxiv updated 2015/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given the query string of length m, we explore a parallel query in a static suffix tree based data structure for p ≪ n, where p is the number of processors and n is the length of the text. We present three results on CREW PRAM. The parallel query in the suffix trie requires O(m + p) work, O(m/p + \lg p) time and O(n2) space in the worst case. We extend the same technique to the suffix tree where we show it is, by design, inherently sequential in the worst case. Finally we perform the parallel query using an interleaved approach and achieve O(m \lg p) work, O((m)/(p) \lg p) time and O(n \lg p) space in the worst case.