BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:2.0
BEGIN:VEVENT
DTSTART:20151117T203000Z
DTEND:20151117T210000Z
LOCATION:18AB
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Suffix arrays and trees are fundamental string data structures of importance to=0Amany applications in computational biology. Consequently, their parallel=0Aconstruction is an actively studied problem. To date, algorithms with best=0Apractical performance lack efficient worst-case run-time guarantees, and vice=0Aversa. In addition, much of the recent work targeted low core count, shared=0Amemory parallelization. In this paper, we present parallel algorithms for=0Adistributed memory construction of suffix arrays and longest common prefix (LCP)=0Aarrays that simultaneously achieve good worst-case run-time bounds and superior=0Apractical performance. Our algorithms run in O(T_sort(n,p)log(n)) worst-case=0Atime where T_sort(n,p) is the run-time of parallel sorting. We present=0Aseveral algorithm engineering techniques that improve performance in practice.=0AWe demonstrate the constructions of suffix and LCP arrays of the human genome in=0Aless than 8 seconds on 1,024 Intel Xeon cores, reaching speedups of over 110X=0Acompared to the best sequential suffix array construction implementation=0Adivsufsort.
SUMMARY:Parallel Distributed Memory Construction of Suffix and Longest Common Prefix Arrays
PRIORITY:3
END:VEVENT
END:VCALENDAR