편집거리 계산을 위한 맵리듀스 알고리즘
MapReduce Algorithms for the Edit Distance Problem
2
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
편집거리는 근사문자열매칭의 대표적인 점수척도로, 길이가 m, n 인 두 문자열에 대한 편집거리는 동적프로그래밍을 이용하여 O(mn) 시간에 계산할 수 있다. 편집거리 계산을 위한 다양한 알고리즘이 연구되고 있으며 그 중에는 병렬 알고리즘에 대한 연구도 포함되어 있다. 본 논문에서는 두 문자열에 대한 편집거리를 계산하는 맵리듀스 알고리즘을 제시한다. O(mn) 시간에 동작하는 Wagner와 Fischer의 알고리즘과 O(mn/t)시간에 동작하는 4-러시안 알고리즘을 각각 맵리듀스 알고리즘으로 변환하고 설명한다. 그리고 맵리듀스 알고리즘들에 대한 이론적인 비용 분석과 함께 제안하는 알고리즘들이 순차 알고리즘보다 시간 효율성을 갖기 위한 조건도 제시한다.
Abstract
The edit distance metric is one of the most widely used scoring metric for the approximate string matching. Given two strings with lengths m and n, we can compute the edit distance between them in O(mn) time using dynamic programming technique. There are several algorithms for the edit distance problem and some of them are parallel algorithms. In this paper, we present two MapReduce algorithms for the edit distance problem between two strings. We convert the Wagner and Fischer algorithm and the Four-Russians algorithms to the MapReduce algorithms and explain them. In addition, we explain some theoretical analysis for our algorithms using a cost model for MapReduce.
참고문헌 (23)
- V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", Sov. Phys. Dokl, 10, pp.707~710 (1966)
- D. Gusfield, "Algorithms on Strings, Trees, and Sequences" (1997), Cambridge University Press
- E. Ukkonen, "Algorithms for approximate string matching", Information and Control, 64, pp.100~118 (1985)
- R. A. Wagner, "The string to string correction problem", J. Assoc. Comput. Mach., 21(1), pp.168~183 (1974)
- W. J. Masek, "A Faster Algorithm Computing String Edit Distance", Journal of Computer and System Sciences, 20(1), pp.18~31 (1980)
- O. Arbell, "Edit distance of run-length encoded strings", Information processing Letters, 83(6), pp.307~314 (2002)
- V. Makinen, "Approximate matching of run-length compressed strings", 12th Annual Symposium on Combinatorial Pattern Matching, 2089, pp.31~49 (2001), LNCS
- R. Lipton, "Comparing long strings on a short systolic array", pp.363~376 (1987), Systolic Arrays
- R. Hughey, "Parallel hardware for sequence comparison and alignment", Computer Applications in the Biosciences, 12(6), pp.473~479 (1996)
- 김영호, "4-러시안 알고리즘 기반의 편집거리 병렬계산", 정보처리학회논문지. 컴퓨터 및 통신시스템, 2(2), pp.67~74 (2013), 한국정보처리학회
- 김영호, "k-오차문제를 위한 4-러시안 알고리즘의 계산 단계 병렬화", 한국차세대컴퓨팅학회 논문지, 9(2), pp.78~88 (2013), 한국차세대컴퓨팅학회
- J. Dean, "MapReduce: Simplified Data Processing on Large Clusters", Communications of the ACM, 51(1), pp.107~113 (2008)
- R. C. Taylor, "An overview of the Hadoop", MapReduce, BMC Bioinformatics, pp.2010, 11(12)[DOI]
- A. Kalyanaraman, "MapReduce implementation of a hybrid spectral library-database search method for large-scale peptide identification", Bioinformatics, 27(21), pp.3072~3073 (2011)
- 이종근, "클라우드 컴퓨팅을 이용한 개인 유전체 정보 분석: 병렬 CNV 영역 검색 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(3), pp.4~11 (2010), 한국차세대컴퓨팅학회
- 이준우, "클라우드 컴퓨팅 기반의 대용량 이동객체 분산 처리 시스템", 한국차세대컴퓨팅학회 논문지, 8(1), pp.42~51 (2012), 한국차세대컴퓨팅학회
- 최동훈, "Hadoop 기반의 그래프 분석을 위한 간선 분할 기법", 한국차세대컴퓨팅학회 논문지, 8(6), pp.17~26 (2012), 한국차세대컴퓨팅학회
- T. Elsayed, "Pairwise document similarity in large collections with MapReduce", 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies, pp.265~268 (2008)
- J. Lin, "Brute force and indexed approaches to pairwise document similarity comparisons with MapReduce", 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp.155~162 (2009)
- F. N. Afrati, "Fuzzy joins using MapReduce", IEEE 28th International Conference on Data Engineering, pp.498~509 (2012)
- S. Jhaver, "Calculating edit distance for large sets of string pairs using MapReduce", 2014 ASE BIGDATA, CYBERSECURITY Conference, pp.2014[DOI]
- Y. Tao, "Minimal MapReduce Algorithms", GMOD'13 (2013)
- A new computation model for cluster computing, "F. N. Afrati", ~ (2009)