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

Efficient representation and parallel computation of string-substring longest common subsequences

Tools
- Tools
+ Tools

Tiskin, Alexander (2006) Efficient representation and parallel computation of string-substring longest common subsequences. In: Joubert, G. R. and Nagel, W. E. and Peters, F. J. and Plata, O. and Tirado, P. and Zapata, E., (eds.) Parallel Computing: Current & Future Issues of High-End Computing,. NIC Series, Volume 33 . John von Neumann Institute for Computing, pp. 827-834. ISBN 3000173528

[img] PDF
827.pdf
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (177Kb)
Official URL: http://webarchiv.fz-juelich.de/nic-series/volume33...

Request Changes to record.

Abstract

Given two strings a, b of length m, n respectively, the string-substring longest common subsequence (SS-LCS) problem consists in computing the length of the longest common subsequence of a and every substring of b. An explicit representation of the output lengths is of size o(n2). We show that the output can be represented implicitly by a set of n two-dimensional integer points, where individual output lengths are obtained by dominance counting queries.This leads to a data structure of size O(n), which allows to query an individual output length in time O( log n log log n), using a recent result by JaJa, Mortensen and Shi. The currently best sequential SS-LCS algorithm by Alves et al. can be adapted to produce the output in the above geometric representation. We also develop a new parallel SS-LCS algorithm that runs
on a p-processor coarse-grained computer in O(mn/p ) local computation, O(n log p) communication,O(log p) barrier synchronisations, and O(n) memory per processor, producing the output in the above geometric representation. Compared to previously known results, our approach presents a substantial improvement in algorithm functionality, output representation efficiency, communication efficiency and/or memory efficiency

Item Type: Book Item
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Series Name: NIC Series
Publisher: John von Neumann Institute for Computing
ISBN: 3000173528
Book Title: Parallel Computing: Current & Future Issues of High-End Computing,
Editor: Joubert, G. R. and Nagel, W. E. and Peters, F. J. and Plata, O. and Tirado, P. and Zapata, E.
Official Date: October 2006
Dates:
DateEvent
October 2006Published
Volume: Volume 33
Page Range: pp. 827-834
Status: Peer Reviewed
Publication Status: Published
Related URLs:
  • Open Access File

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