sponsored byIEEEACMThe International Conference for High Performance 
Computing, Networking, Storage and Analysis
FacebookTwitterGoogle PlusLinkedInYouTubeFlickr

SCHEDULE: NOV 16-21, 2014

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Fast Parallel Computation of Longest Common Prefixes

SESSION: Parallel Algorithms


TIME: 4:30PM - 5:00PM


AUTHOR(S):Julian Shun



Suffix arrays and the corresponding longest common prefix (LCP) array
have wide applications in bioinformatics, information retrieval and
data compression. In this work, we propose and theoretically analyze
new parallel algorithms for computing the LCP array given the suffix
array as input. Most of our algorithms have a work and depth
(parallel time) complexity related to the LCP values of the input. We
also present a slight variation of Karkkainen and Sanders'
skew algorithm that requires linear work and poly-logarithmic depth in
the worst case. We present a comprehensive experimental study of our
parallel algorithms along with existing parallel and sequential LCP
algorithms. On a variety of real-world and artificial strings, we
show that on a 40-core shared-memory machine our fastest algorithm is
up to 2.3 times faster than the fastest existing parallel algorithm,
and up to 21.8 times faster than the fastest sequential LCP algorithm.

Chair/Author Details:

Judith C. Hill (Chair) - Oak Ridge National Laboratory

Julian Shun - Carnegie Mellon University

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society