106 0

Full metadata record

DC FieldValueLanguage
dc.contributor.author박희진-
dc.date.accessioned2019-04-12T05:34:06Z-
dc.date.available2019-04-12T05:34:06Z-
dc.date.issued2016-12-
dc.identifier.citationTHEORETICAL COMPUTER SCIENCE, v. 656, NO. 20, Page. 173-179en_US
dc.identifier.issn0304-3975-
dc.identifier.issn1879-2294-
dc.identifier.urihttps://www.sciencedirect.com/science/article/pii/S0304397516300676?via%3Dihub-
dc.identifier.urihttps://repository.hanyang.ac.kr/handle/20.500.11754/101819-
dc.description.abstractGiven two strings X (|X| = m) and Y (|Y| = n) over an alphabet Sigma, the edit distance between X and Y can be computed in 0 (mn/t) time with the help of the Four Russians' lookup table whose block size is t. The Four-Russians' lookup table can be constructed in O ((3|Sigma|)(2t)t(2)) time using O((3|Sigma|(2t)t) space. However, the construction time and space requirement of the lookup table grow very fast as the alphabet size increases and thus it has been used only when |Sigma| is very small. For example, when a string is a protein sequence, |Sigma| = 20 and thus it is almost impossible to use the Four-Russians' lookup table on typical workstations. In this paper, we present an efficient alphabet-independent Four-Russians' lookup table. It requires O (3(2t)(2t)!t) space and can be constructed in O (3(2t)(2t)!t(2)) time. Thus, the Four-Russians' lookup table can be constructed and used irrespective of the alphabet size. The time and space complexity were achieved by compacting the lookup table using a clever encoding of the preprocessed strings. Experimental results show that the space requirement of the lookup table is reduced to about 1/5,172,030 of its original size when |Sigma| = 26 and t = 4. Furthermore, we present efficient multithreaded parallel algorithms for edit distance computation using the Four Russians' lookup table. The parallel algorithm for lookup table construction runs in O(t) time and the parallel algorithm for edit distance computation between X and Y runs in O (m + n) time. Experiments performed on CUDA-supported GPU show that our algorithm runs about 942 times faster than the sequential version of the original Four-Russians' algorithm for 100 pairs of random strings of length approximately 1,000 when |Sigma| = 4 and t = 4. (C) 2016 Elsevier B.V. All rights reserved.en_US
dc.description.sponsorshipJoong Chae Na was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2014R1A1A1004901). Heejin Park was supported by the research fund of Signal Intelligence Research Center supervised by Defense Acquisition Program Administration and Agency for Defense Development of Korea. Jeong Seop Sim was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIP) (No. 2014R1A2A1A11050337) and by the Genome Program for Fostering New Post-Genome industry of the National Research Foundation (NRF) & funded by the Korean government (MSIP) (NRF-2014M3C9A3064706).en_US
dc.language.isoenen_US
dc.publisherELSEVIER SCIENCE BVen_US
dc.subjectApproximate string matchingen_US
dc.subjectEdit distanceen_US
dc.subjectFour-Russians' algorithmen_US
dc.subjectParallelizationen_US
dc.titleA space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithmen_US
dc.typeArticleen_US
dc.relation.no20-
dc.relation.volume656 Part B-
dc.identifier.doi10.1016/j.tcs.2016.04.028-
dc.relation.page173-179-
dc.relation.journalTHEORETICAL COMPUTER SCIENCE-
dc.contributor.googleauthorKim, Youngho-
dc.contributor.googleauthorNa, Joong Chae-
dc.contributor.googleauthorPark, Heejin-
dc.contributor.googleauthorSim, Jeong Seop-
dc.relation.code2016002626-
dc.sector.campusS-
dc.sector.daehakCOLLEGE OF ENGINEERING[S]-
dc.sector.departmentDEPARTMENT OF COMPUTER SCIENCE-
dc.identifier.pidhjpark-
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE