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)

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:	Date Event October 2006 Published
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