BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20141118T223000Z
DTEND:20141118T230000Z
LOCATION:391-92
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Suffix arrays and the corresponding longest common prefix (LCP) array=0Ahave wide applications in bioinformatics, information retrieval and=0Adata compression. In this work, we propose and theoretically analyze=0Anew parallel algorithms for computing the LCP array given the suffix=0Aarray as input. Most of our algorithms have a work and depth=0A(parallel time) complexity related to the LCP values of the input. We=0Aalso present a slight variation of Karkkainen and Sanders'=0Askew algorithm that requires linear work and poly-logarithmic depth in=0Athe worst case. We present a comprehensive experimental study of our=0Aparallel algorithms along with existing parallel and sequential LCP=0Aalgorithms. On a variety of real-world and artificial strings, we=0Ashow that on a 40-core shared-memory machine our fastest algorithm is=0Aup to 2.3 times faster than the fastest existing parallel algorithm,=0Aand up to 21.8 times faster than the fastest sequential LCP algorithm.
SUMMARY:Fast Parallel Computation of Longest Common Prefixes
PRIORITY:3
END:VEVENT
END:VCALENDAR