초록 ▼

□ 연구개요
빅 데이터 환경에서의 비정형 (informal) 데이터를 분석하기 위해서는 완전 일치 패턴보다 근사화 패턴이 더 활용도가 높아질 것으로 예상된다. 또한 근사화 패턴에서 다양한 종류의 분화 연산이 고려되고 여러 패턴의 매칭 다양성이 고려된다면 실제 패턴들의 근사화를 더욱 정밀하게 모델링하는 것이 가능하다. 그러므로 패턴 분화의 여러 연산과 여러 패턴들에 대한 매칭 다양성을 고려하는 고속의 근사화 패턴 매칭기술이 꼭 필요하다. 본 과제는 기존의 소프트웨어 기반 패턴 매칭 엔진을 대신하는 GPU (graphic proc

□ 연구개요
빅 데이터 환경에서의 비정형 (informal) 데이터를 분석하기 위해서는 완전 일치 패턴보다 근사화 패턴이 더 활용도가 높아질 것으로 예상된다. 또한 근사화 패턴에서 다양한 종류의 분화 연산이 고려되고 여러 패턴의 매칭 다양성이 고려된다면 실제 패턴들의 근사화를 더욱 정밀하게 모델링하는 것이 가능하다. 그러므로 패턴 분화의 여러 연산과 여러 패턴들에 대한 매칭 다양성을 고려하는 고속의 근사화 패턴 매칭기술이 꼭 필요하다. 본 과제는 기존의 소프트웨어 기반 패턴 매칭 엔진을 대신하는 GPU (graphic processing unit) 기반의 병렬 근사화 패턴 매칭 엔진 의 연구를 수행한다. 이를 통해 고성능의 Levenshtein distance를 고려한 병렬 근사화 패턴 매칭 알고리즘을 개발하고 구현하는 것을 목표로 한다.

□ 연구 목표대비 연구결과
본 연구의 목표의 최종 목표는 멀티 패턴에 대해 Levenshtein distance를 고려한 병렬 근사화 문자열 패턴 매칭 알고리즘 개발 및 구현이다. 해당 목표를 달성하기 위해 본 연구에서는 이에 대한 구체적인 병렬 근사화 패턴 매칭 알고리즘에 대한 이론 및 기초 구현에 대한 연구를 수행하였다.
1차년도에서는 패턴의 분화의 범위에 따른 데이터구조와 연산을 제안, 근사화 패턴매칭의 다양성을 고려한 연산 알고리즘을 개발하고, GPU를 이용한 근사화 패턴 매칭 엔진의 성능 향상을 위한 데이터와 연산 구조를 제시하였다.
2차년도에서는 멀티 패턴을 지원하는 병렬 근사화 패턴 매칭 알고리즘에 대한 연구를 수행하였다. 이에 따라 멀티패턴에서의 적절한 distance metric을 제시하였다. 또한 distance를 계산하기 위한 연산량을 줄이기 위해 pruning bit를 이용하여 불필요한 distance 계산 연산을 줄이고 병렬처리가 가능한 방법에 대한 연구를 진행하였다.
3차년도에서는 범용적인 라이브러리 개발에 따라 pruning을 이용하여 연산을 줄이는 방법에 대해 구현 및 분석을 수행하였다. 이 경우 단순한 형태의 Levenshtein distance와 키보드 및 문자 형태의 유사함을 고려하여 distance를 계산하고, 이에 따라 해당 라이브러리를 적용시의 문제점을 분석하였다. 일반적인 Levenshtein distance과 키보드 및 문자 모양을 고려하는 등의 복잡한 distance metric을 사용하는 경우, 단순한 metric에서는 pruning을 이용한 방법을 사용해서는 성능향상이 미비하고, 복잡한 metric에서 큰 성능향상을 얻을 수 있었다.

□ 연구개발결과의 중요성
본 연구의 기술적 성과는 여러 가지 분화된 패턴들에 대한 매칭을 수행할 수 있는 범용적인 적용이 가능한 병렬 근사화 문자열 패턴 매칭 알고리즘 개발 및 구현 기술의 확보이다. Levenshtein distance를 고려한 병렬 근사화 패턴 매칭 알고리즘은 다양한 어플리케이션에 적용될 수 있는 범용성을 가질 수 있다. 또한 연구될 패턴 매칭 알고리즘의 개발과 구현은 복잡도가 늘어나는 빅 데이터 분석에 있어서 예측 가능한 성능을 얻음으로써 다양한 어플리케이션에 적용 가능성을 높일 수 있다. 본 연구의 과정은 GPU 구조 기반의 근사화 패턴 매칭을 위한 알고리즘의 개발에서부터 응용을 위한 라이브러리 구현까지 포함한다. 따라서 본 연구를 통해 GPU를 이용한 가속기 구조에 대한 전문 지식을 갖추고, 소프트웨어를 동시 개발에 능숙한 우수한 전문 인력을 양성할 수 있었다.

(출처 : 연구결과 요약문 3p)

목차 Contents

• 표지 ... 1
• 연구결과 요약문 ... 3
• 목차 ... 4
• 1. 연구개발과제의 개요 ... 4
• 2. 연구수행내용 및 연구결과 ... 4
• 1. 1차년도 ... 4
• 2. 2차년도 ... 7
• 3. 3차년도 ... 9
• 3. 연구개발결과의 중요성 ... 11
• 4. 참고문헌 ... 11
• 5. 연구성과 ... 12
• 끝페이지 ... 13