메뉴 건너뛰기
Library Notice
Institutional Access
If you certify, you can access the articles for free.
Check out your institutions.
ex)Hankuk University, Nuri Motors
Log in Register Help KOR
Subject
Humanities
General Humanities History Philosophy Religious Studies Linguistics and Literature Other Humanities
Social science
General Social Science Business Management Tourism Education Military Science Library and Information Science Law Sociology Journalism and Media Studies Psychological Science Political Science and Diplomacy Geography Public Administration Economics International Trade Anthropology Other Social Science
Natural science
General Natural Science Physics Biology Life Sciences Mathematics/Statistics Astronomy Earth Science Chemistry Other Natural Science
Engineering
General Engineering Architectural Engineering Mechanical Engineering Industrial Engineering Material/Energy Engineering Electrical and Electronic Engineering Marine and Ocean Engineering Chemical Engineering Computer Science Other Engineering
Medical science
General Medical Science Nursing Science Veterinary Pharmacy Traditional Korean Medicine Basic Medicine Clinical Medicine Other Medicine
Agriculture and Fishery
General Agriculture and Fishery Agriculture Fishery Science Food Science Forestry Animal Husbandry Marine Transportation Studies Other Agriculture and Fishery
Art and Kinesiology
General Arts Design Fine Arts Cosmetology Photography Music Fashion Kinesiology Performing Media Arts Other Arts and Kinesiology
Interdisciplinary Studies
Interdisciplinary Research Science and Technology Studies Brain and Cognitive Science Technology Policy Other Interdisciplinary Studies

KOR

Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets
Recommendations
Search
Questions

정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘

논문 기본 정보

Type
Academic journal
Author
Youngho Kim (인하대학교) Jeong Seop Sim (인하대학교)
Journal
Korean Institute of Information Scientists and Engineers Journal of KIISE Vol.44 No.8 KCI Excellent Accredited Journal
Published
2017.8
Pages
760 - 766 (7page)
DOI
10.5626/JOK.2017.44.8.760

Usage

cover
📌
Topic
📖
Background
🔬
Method
🏆
Result
Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets
Ask AI
Recommendations
Search
Questions

Abstract· Keywords

Report Errors
Repetitive strings have been studied in diverse fields such as data compression, bioinformatics and so on. Recently, two problems of approximate periods of strings over integer alphabets were introduced, finding minimum δ-approximate periods and finding minimum γ-approximate periods. Both problems can be solved in O(n²) time when n is the length of the string. In this paper, we present two parallel algorithms for solving the above two problems in O(n²) time using O(n²) threads, respectively. The experimental results show that our parallel algorithms for finding minimum δ-approximate (resp. γ-approximate) periods run approximately 19.7 (resp. 40.08) times faster than the sequential algorithms when n = 10,000.
#반복문자열 #근사문자열매칭 #δ-근사주기 #γ-근사주기 #병렬알고리즘 #CUDA #repetitive strings #approximate string matching #δ-approximate periods #γ-approximate periods #parallel algorithm

Contents

요약
Abstract
1. 서론
2. 관련 연구
3. 최소 δ-근사주기와 최소 γ-근사주기 병렬 계산 알고리즘
4. 실험 결과
5. 결론
References

References (13)

Add References
M. Burrows, D. J. Wheeler, A Block-sorting Lossless Data Compression Algorithm, Technical report 124. Palo Alto, CA: Digital Equipment Corporation, 1994. A. T. Castelo, W. Martins and G. R. Gao, TROLL ?Tandem Repeat Occurrence Locator, Bioinformatics, Vol. 18, No. 4, pp. 634-636, 2002. A. Apostolico, D. Breslauer, An Optimal  loglog  Time Parallel Algorithm for Detecting all Squares in a String, SIAM Journal on Computing, Vol. 25, No. 6, pp. 1318-1331, 1996. J. S. Sim, C. S. Iliopoulos, K. Park, W. F. Smyth, Approximate periods of strings, Theoretical Computer Science, Vol. 262, pp. 557-568, 2001. J. H. Jeong, Y. H. Kim, J. C. Na, J. S. Sim, Approximate periods of strings based on distance sum for DNA sequence analysis, KIPS Transactions on Software and Data Engineering, Vol. 2, No. 2, pp. 119-122, 2013. (in Korean)

Recommendations

It is an article recommended by DBpia according to the article similarity. Check out the related articles!

Related Authors

Frequently Viewed Together

Z-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산
Youkun Shin ,  Youngho Kim ,  Jeong Seop Sim Journal of KIISE 2018 .08

Recently viewed articles

APCC 다중 모형 자료 기반 계절 내 월 기온 및 강수 변동 예측성
송찬영, 김응섭, 안중배Korean Meteorological Society2020.10
 The Specially Designed Pattern Based Compound Distortion Correction Method and Its Verification
Minjung Lee, Hyungtae Kim, Younghoon Lim 외 2명The Institute of Electronics and Information Engineers2017.06
 토지이용규제와 환경규제의 연계성 확보
채미옥Korea Research Institute For Human Settlements2003.06
 LSTM-Based Human Fall Detection using Thermal Array Sensor
Adinda Riztia Putri, Goodness Oluchi Anyanwu, Mareska Pratiwi Maharani 외 2명Korea Institute Of Communication Sciences2021.06

Comments(0)

0

Write first comments.