Title:
LCS Algorithm for Big Data Flows1
Author:
Type:
Co-author(s) :
Uncontrolled Keywords:
LCS ; online algorithm ; parallelization ; iteration ; datastructure
Abstract:
The Longest Common Subsequence (LCS) problem is aimed at constructing a maximum length subsequence, common to a given set of sequences, defined on some finite alphabet of symbols. The paper, without loss of generality considers the particular case of two input sequences. We consider the problem in an online fashion, where symbols arrive one-byone and the next acquired symbol is appending any one of the two input sequences. The sought-for LCS algorithm acts by recursive handling of parts of sequences arrival so far, constructing and updating specific structures of markers representing the interrelations of the longest common subsequences of the two input sequences. In paper we present a perfect online parallelization of that algorithm for the “simple” memory model, so that the parallel complexity becomes O �� � for � parallel threads.
Language:
URL:
Affiliation:
Institute for Informatics and Automation Problems
Country:
Year:
Time period:
Conference title:
11th International Conference on Computer Science and Information Technologies CSIT 2017