벡터 사분트리를 이용한 병렬 공간 조인 = Parallel Spatial Join using Vector Quadtress

국문 초록 (Abstract)

지리 정보 시스템에서 공간 분석을 위해 사용되는 중요한 연산인 공간 조인은 대상이 되는 공간 객체의 수가 증가함에 따라서 연산 시간이 지수적으로 증가하는 특징을 가지고 있다. 그러므로 다량의 공간 데이타에 대해서 공간 연산 시간을 줄이기 위한 병렬 처리 기법이 필요하다.
이 논문에서는 비겹침 정규 분할 방식의 사분트리를 이용한 공간 조인 알고리즘을 제시하고 MIMD 구조 및 공유 디스크 방식의 병렬 처리 시스템에 적용하여 성능을 평가한다. 사분트리를 이용한 공간 조인 방법으로서 중복 표현된 공간 객체를 줄이기 위한 사분면(quadrant)의 병합 방법, 영역 제한을 통해 연산대상 객체를 줄이기 위한 사분면의 분할 방법, 그리고 병합 및 분할 방법을 혼용하여 공간 조인 연산의 숫자를 최소화하는 혼합 방법을 제시한다. 실험 평가에서는 각 방법들을 병렬 처리 시스템에 적용하여 여과 단계 및 정제 단계에서의 연산량과 수행 시간을 통해 성능을 비교 평가한다. 실험결과, 여과 단계에서는 분할 방법이 가장 우수했지만, 정제 단계에서는 병합 방법이 가장 우수했다. 따라서 전체적인 성능을 고려할 때 두 방법의 장점을 수용한 혼합 방법이 가장 우수한 성능을 나타내었다.

다국어 초록 (Multilingual Abstract)

Spatial join is required for processing spatial analysis in GIS. The cost of a spatial join is exponentially increased in proportion to the number of spatial objects. The motivation of this work is to use parallel processing techniques for reducing the time of execution of a spatial join on a large volume of spatial data.
This paper proposes three kinds of parallel spatial join algorithms using the disjoint regular quad tree. One is the quad-merge method to reduce the duplicated representation, another is the quad-split method to restrict the search space of spatial join, and other is the hybrid method to minimize the number of spatial join operations by combining above the two methods. The parallel spatial join algorithms are evaluated on the parallel processing system With MIMD and shared disk. Performance evaluation is achieved by measurement of the number of operations and execution time in both the filtering step and the refinement step for each algorithm. This experimental test shows that the quad-split method works best in the filtering step, but the quad-merge method works best in the refinement step. As the result of the overall experimental performance comparison, it is shown that the hybrid method, which combines the quad-split method and the quad-merge method, is better than the others.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 공간 조인
• 4. 병렬 처리
• 5. 실험 평가
• 6. 결론 및 향후 연구 과제
• 참고문헌
• 저자소개