구석점 변환 기법을 이용한 공간 조인 알고리즘 = Spatial Join Algorithm using Corner Transformation

국문 초록 (Abstract)

공간조인은 공간 데이타베이스 시스템에서 특징 공간 관계를 가지는 객체쌍들을 찾기 위한 연산이다. 공간조인은 처리 비용이 아주 큰 연산이므로, 제공되는 공간 액세스 방법의 특성을 충분히 이용하는 효율적인 알고리즘이 연구되어야 한다. 본 논문에서는 구석점 변환 기법을 이용한 공간조인 알고리즘을 제안하고, 분석과 실험을 통하여 그 우수성을 입증한다. 우리들이 아는 바로는 변환 기법을 이용한 공간조인 알고리즘은 아직 연구된 바 없다. 구석점 변환 기법에서는 한 화일의 인접한 두 영역에 대한 상대방 화일의 두 조인 대상 영역은 많은 공통 부분을 가진다. 제안된 알고리즘에서는 이러한 특성을 이용하여 공간 조인 처리에 필요한 디스크 액세스 횟수를 줄인다. 실험 결과 제안된 알고리즘은 Brinkhoff 등이 제안한 R* -tree를 이용한 알고리즘보다 일반적으로 나은 성능을 가진다. 이는 구석점 변환 기법이 공간 액세스 방법의 우수한 한 부류이며 공간 질의가 원공간보다 변환 공간에서 더 잘 처리될 수 있다는 좋은 징표라 할 수 있다. 이는 변환 기법이 클리스터링 성질을 유지 못한다는 일반적인 믿음은 뒤엎는 결과이다. 우리는 이 결과가 공간 질의에 대한 변환 공간 기반 처리라는 새로운 방향을 제시한다고 믿는다.

다국어 초록 (Multilingual Abstract)

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database system Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through analysis and experiments. To the extent of authors' knowledge, the spatial join algorithm using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join Experimental results show that the algorithm has a generally better performance than the R* tree based algorithm proposed by Brinkhoff et al. This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering We believe that our results will provide a new insight towards transformation based processing of spatial operations.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 구석점 변환 기법
• 3. 공간조인 알고리즘
• 4. 성능 평가
• 5. 결론
• 참고문헌
• 부록
• 저자소개