궤적정보 이상치 검출 병렬 알고리즘 최적화 기법

Abstract

Recently, large-scale trajectory dataset is rapidly increasing with the development of GPS and various basic technologies. However, trajectory outlier detection algorithm TRAOD[3], which many researchers are using, has a performance problem in processing such a large amount of trajectory dataset. In order to solve this problem, this study solved the performance issue by parallelizing TRAOD on GPU and applying various optimization methods. There were two main challenges here. The first is that the length of each trajectory in the data set is different from each other, making it difficult to parallelize it. Second, as suggested by guan et al (2012), the use of R-trees for TRAOD can improve performance, but it is not designed to take into account the GPU environment, which can cause various performance degradation factors when encountering the GPU. In order to overcome these two challenges, this study devised a GPU-friendly R-tree indexing technique and a matrix shape transformation technique to help parallelization. Through the above optimization methods, we proposed a parallel TRAOD algorithm that is 300 times faster than CPU version and 15 times faster than GPU version baseline. In addition, TRAOD was applied to digital tachograph and military trajectory to perform visual commentary about trajectory outlier and quantitative evaluation of each outlier.

최근 GPS 및 여러 기반기술들이 발달하면서 대용량 궤적정보가 급증하고 있다. 하지만 많은 연구자들이 활용하고 있는 궤적정보 이상치 탐지 알고리즘 TRAOD[3]는 이러한 대용량 궤적정보를 처리하는 데에는 속도 측면의 어려움이 있다. 이러한 문제를 해결하기 위해, 본 연구에서는 TRAOD를 GPU 환경에 맞게 병렬화하고 여러 가지 최적화기법을 적용하여 속도문제를 해결하였다. 여기에는 크게 2가지의 도전과제 (Challenge)가 있었는데, 첫째는 데이터 집합 내 각 궤적의 길이가 서로 달라 규격화되어 있지 않은 자료구조를 지니고 있어 병렬화가 어렵다는 점이고, 두 번째는 Guan et al (2012)이 제안한 것[11]처럼 TRAOD에도 R-tree를 활용하면 성능을 향상시킬 수 있는데, 이는 GPU 환경을 고려하고 설계된 것이 아니기 때문에 GPU와 만났을 때, 여러 가지 성능저하가 발생할 수 있다는 점이다. 위 2가지 도전과제를 극복하기 위해, 본 연구에서는 GPU에 친화적인 R-tree 인덱싱, 병렬화가 쉽도록 도와주는 행렬 형태 변형 기법을 고안하여 CPU버전 대비 300배, GPU버전 베이스라인 대비 15배의 성능향상을 산출할 수 있는 병렬 TRAOD 알고리즘을 제안하였다. 추가로 디지털운행기록정보와 군사궤적정보에 TRAOD를 적용시켜 각 이상치에 대한 시각적 해설과 정량적 평가까지 첨부하였다.