Անվանում:
LCS Algorithm for Big Data Flows1
Հեղինակ:
Տեսակ:
Համահեղինակ(ներ):
Չվերահսկվող բանալի բառեր:
LCS ; online algorithm ; parallelization ; iteration ; datastructure
Ամփոփում:
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.
Լեզու:
URL:
Կազմակերպության անվանում:
Institute for Informatics and Automation Problems
Երկիր:
Տարի:
Ժամանակահատված:
Գիտաժողովի անվանում:
11th International Conference on Computer Science and Information Technologies CSIT 2017