Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

New algorithms for efficient parallel string comparison

Tools
- Tools
+ Tools

Krusche, Peter and Tiskin, Alexander (2010) New algorithms for efficient parallel string comparison. In: 22nd ACM Symposium on Parallelism in Algorithms and Architectures, Santorini, Greece, 13-15 Jun 2010. Published in: SPAA '10: Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures pp. 209-216. ISBN 9781450300797. doi:10.1145/1810479.1810521

[img] Text
p209-krusche.pdf
Embargoed item. Restricted access to Repository staff only

Download (593Kb)
Official URL: http://dx.doi.org/10.1145/1810479.1810521

Request Changes to record.

Abstract

In this paper. we show new parallel algorithms for a set of classical string comparison problems. computation of string alignments. longest common subsequences (LCS) or edit distances, and longest increasing subsequence computation. These problems have a wide range of applications, in particular in computational biology and signal processing. We discuss the scalability of our new parallel algorithms in computation time, in memory, and in commumcation Our new algorithms are based on an efficient parallel method for (min, +)-multiplication of distance matrices The core result of this paper is a scalable parallel algorithm for multiplying Implicit simple unit-Monge matrices of size n x n on p processors using lime O(n log n/p), communication O(n log p/p) and O( log p) supersteps. This algorithm allows us to implement scalable LCS computation for two strings of length n using time O(n(2)/p) and communication O(n/root P) requiring local memory of size O(n/root P) on each processor Furthermore, our algorithm can be used to obtain the first generally work-scalable algorithm for computing the longest increasing subsequence (LIS) Our algorithm for LIS computation requires computation O(n log(2) n/p), communication O(n log(2) p/p), and O(log(2) p) supersteps for computing the LIS of a sequence of length n This is within a log n factor of work-optimality for the LIS problem. which can be solved sequentially in time O(n log n) in the comparison-based model. Our LIS algorithm is also within a log p-factor of achieving perfectly scalable communication and furthermore has perfectly scalable memory size requirements of O(n/p) per processor

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title: SPAA '10: Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures
Publisher: Assoc. Computing Machinery
ISBN: 9781450300797
Official Date: 13 June 2010
Dates:
DateEvent
13 June 2010Published
Number of Pages: 8
Page Range: pp. 209-216
DOI: 10.1145/1810479.1810521
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Conference Paper Type: Paper
Title of Event: 22nd ACM Symposium on Parallelism in Algorithms and Architectures
Type of Event: Other
Location of Event: Santorini, Greece
Date(s) of Event: 13-15 Jun 2010
Related URLs:
  • Organisation

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us