TY - GEN

T1 - Parallel suffix array construction by accelerated sampling

AU - Pace, Matthew Felice

AU - Tiskin, Alexander

PY - 2013/10/1

Y1 - 2013/10/1

N2 - A deterministic BSP algorithm for constructing the suffix array of a given string is presented, based on a technique that we call accelerated sampling. It runs in optimal O(np) local computation and communication, and requires a near optimal O(log logp) supersteps. The algorithm provides an improvement over the synchronisation costs of existing algorithms, and reinforces the importance of the sampling technique. © Czech Technical University in Prague, Czech Republic.

AB - A deterministic BSP algorithm for constructing the suffix array of a given string is presented, based on a technique that we call accelerated sampling. It runs in optimal O(np) local computation and communication, and requires a near optimal O(log logp) supersteps. The algorithm provides an improvement over the synchronisation costs of existing algorithms, and reinforces the importance of the sampling technique. © Czech Technical University in Prague, Czech Republic.

KW - Accelerated sampling

KW - BSP

KW - Suffix array

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

M3 - Conference contribution

AN - SCOPUS:84884653802

SP - 142

EP - 156

BT - Proceedings of the Prague Stringology Conference 2013, PSC 2013

ER -