The Library
Efficient representation and parallel computation of stringsubstring longest common subsequences
Tools
Tiskin, Alexander (2006) Efficient representation and parallel computation of stringsubstring 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 HighEnd Computing,. NIC Series, Volume 33 . John von Neumann Institute for Computing, pp. 827834. ISBN 3000173528
PDF
827.pdf Embargoed item. Restricted access to Repository staff only  Requires a PDF viewer. Download (177Kb) 
Official URL: http://webarchiv.fzjuelich.de/nicseries/volume33...
Abstract
Given two strings a, b of length m, n respectively, the stringsubstring longest common subsequence (SSLCS) 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 twodimensional 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 SSLCS algorithm by Alves et al. can be adapted to produce the output in the above geometric representation. We also develop a new parallel SSLCS algorithm that runs
on a pprocessor coarsegrained 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 HighEnd 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. 827834  
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 