The Library
Efficient representation and parallel computation of string-substring longest common subsequences
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
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...
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, Engineering and Medicine > 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: |
|
||||
Volume: | Volume 33 | ||||
Page Range: | pp. 827-834 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |