디지털 라이브러리[ 검색결과 ]
2개의 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭알고리즘
http://doi.org/10.5626/JOK.2018.45.11.1111
순위패턴매칭문제는 길이가 각각 n, m인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위가 같은 T의 모든 부분문자열을 찾는 문제이다. 최근 q-그램의 핑거프린트를 이용한 O(nm + nqlogq +q!) 시간 순위패턴매칭 알고리즘이 제시되었다. 본 논문에서는 2개의 q-그램에 대한 핑거프린트를 이용하여 수행시간을 개선한 순위패턴매칭 알고리즘을 제시한다. 실험 결과, 본 논문에서 제시하는 알고리즘은 기존의 알고리즘보다 무작위로 생성된 T(n = 5,000,000)와 P(m = 5,10,15)에 대해 최대 약 12% 빠르게 수행된다. 또한 다우존스지수 데이터를 이용한 T(n = 34,658)와 T에서 무작위로 추출한 P(m = 5,10,15)에 대해 최대 약 10% 빠르게 수행된다.
효율적인 데이터 중복제거를 위한 GPGPU 병렬 라빈 핑거프린팅
데이터 중복 제거를 수행하기 위한 여러 단계 중 청킹에 사용되는 라빈 핑거프린트 값을 구하는 단계가 가장 큰 오버헤드를 차지한다. 따라서, 본 논문에서는 효율적인 데이터 중복 제거를 위한 병렬라빈 핑거프린트 방법을 제안한다. 또한 효율적인 라빈 핑거프린팅의 병렬화를 위해 네 가지 이슈를 고려한다. 첫 번째로 병렬처리를 위해 입력 데이터 스트림을 일정한 크기의 데이터 섹션으로 분할할 때, 데이터 섹션의 경계선에 있는 데이터들에 대해서도 라빈 핑거프린팅을 수행하기 위한 고려, 두 번째로 라빈핑거프린팅 연산 특징을 효율적으로 이용하기 위한 고려, 세 번째로 순차 방식으로 청크 경계선을 구했을 때와 비교하여 병렬 방식으로 청크 경계선을 구했을 때, 변경 될 수 있는 청크 경계선에 대한 고려를 한다. 마지막으로 최적의 GPGPU 메모리 접근을 위한 고려를 한다. GPGPU를 이용한 병렬 라빈 핑거프린트 방식은 CPU를 이용한 순차 라빈 핑거프린트 방식에 비해 약 16배 성능향상을 보였고, CPU를 이용한 병렬 라빈 핑거프린트 방식에 비해서도 약 5.3배 성능향상을 보였다. 이러한 라빈 핑거프린팅 연산 처리량의 증가는 데이터 중복 제거 기법의 전체적인 성능향상을 가져올 수 있다.
