2013/02/23 by Matthew Felice Pace, Pace, Matthew Felice, Alexander Tiskin +1
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #F.1.2 #F.2.2 #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1302.5851
12 pages
arxiv created 2013/02/23 · arxiv updated 2013/02/26
A deterministic BSP algorithm for constructing the suffix array of a given string is presented, based on a technique which we call accelerated sampling. It runs in optimal O(n/p) local computation and communication, and requires a near optimal O(log log p) synchronisation steps. The algorithm provides an improvement over the synchronisation costs of existing algorithms, and reinforces the importance of the sampling technique.