Spatial joins find all pairs of objects that satisfy a given spatial relationship. Since they play key roles in spatial databases and require a significant cost of processing, efficient spatial join algorithms are crucial for improving performance of spatial databases. Existing spatial join algorithms are classified into those that use indexes and those that do not.
In the first part of this dissertation, we present a new spatial join algorithm that uses indexes. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space index is the one that indexes objects as represented in the original space. Since original-space indexes deal with extents of objects, it is relatively complex to optimize join algorithms using these indexes. On the other hand, a transform-space index, which transforms objects in the original space into points in the transform space and indexes them, deals only with points but no extents. Thus, optimization of join algorithms using these indexes can be more formal. However, the disadvantage of these algorithms is that they cannot be applied to original-space indexes such as the R-tree.
In this dissertation, we present a novel mechanism for achieving the best of these two types of algorithms. Specifically, we propose a new notion of the transform-space view and present the transform-space view join algorithm. A transform-space view is a virtual transform-space index based on an original-space index. It allows us to "interpret" or "view" an existing original-space index as a transform-space index without incurring any overhead and without actually modifying the structure of the original-space index or changing object representation. The transform-space view join algorithm joins two original-space indexes in the transform space through the notion of the transform-space view.
In a transform-space view join algorithm, the order of accessing disk pages-for which various space filling curves could be used-makes a significant impact on the performance of joins. In this paper, we propose a new space filling curve called the adaptive row major order (ARM order). The ARM order adaptively controls the order of accessing pages and significantly improves the performance. Through analysis and experiments, we verify excellence of the ARM order. Compared to other conventional space filling curves used with the transform-space view join and existing spatial join algorithms that use R-trees in the original space, the ARM order always outperforms existing ones in terms of the one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page), the number of disk accesses for a given buffer size, and the wall clock time-thus, constituting a lower bound algorithm. Specifically, compared to other conventional space filling curves used with the transform-space view join, the ARM order reduces the one-pass buffer size by up to 21.3 times and improves the number of disk accesses by up to 74.6%. Compared to existing spatial join algorithms that use R-trees in the original space, the transform-space view join reduces the one-pass buffer size by up to 15.7 times and improves the number of disk accesses by up to 65.3%. The results of the wall clock time have a similar trend to that of the number of disk accesses.
In the second part of this dissertation, we present a new spatial join algorithm that does not use indexes. Spatial joins that do not use indexes divide the spaces of the two files to be joined into partitions and distribute the spatial objects in the files to the partitions. Next, they join every pair of partitions that satisfy join relationship. Here, since the objects in the original space have extents, those located at an edge of a partition might intersect with two or more partitions. If objects are replicated into all the partitions that they intersect, this replication dramatically degrades the performance depending on data distributions and also causes duplicates in the join result. If, to avoid replications, complex structures of partitions are used, join relationship between partitions becomes complex, resulting in performance degradation. The reason why the existing algorithms need either replication of spatial objects or complex partition structures is that the spatial objects have extents causing them to possibly intersect with more than one partition. If we eliminate the extents of the spatial objects by transforming the objects from the original space into the points in the transform space, then we can make the transformed objects belong to only one partition. Therefore, we can develop a more efficient join algorithm.
In this dissertation, we propose the notion of the transform-space partition and present the transform-space partition join algorithm to solve the problems of existing join algorithms without using indexes. The proposed algorithm divides the trans-form space into transform-space partitions and joins every pair of transform-space partitions that satisfy join relationship. Since the algorithm deals only with points having no extents, it has advantages over existing ones in that 1) it obviates the need for replicating spatial objects, and 2) its partition structure is simple. As a result, it always has better performance compared to existing algorithms. Extensive experiments show that our algorithm improves performance by 20.5~38.0% over the existing algorithms compared.
In summary, the dissertation proposes the new notions of the transform-space view and transform-space partition and presents two new join algorithms using these notions. The proposed notions and algorithms solve various problems of the existing algorithms thereby improving performances. We believe that the proposed notions and algorithms provide a framework for developing various new spatial query processing algorithms in the transform space.
공간 조인이란 주어진 공간 관계를 만족하는 모든 공간 객체들의 쌍을 찾는 질의이다. 공간 조인은 공간 데이터베이스 시스템의 기본이 되는 연산중의 하나로, 많은 디스크 I/O와 처리시간을 필요로 하는 연산이다. 따라서, 이를 효과적으로 처리하는 알고리즘의 개발은 공간 데이터베이스 성능의 향상을 위해 꼭 필요한 연구이다. 공간 조인 알고리즘은 공간 색인의 사용 여부에 따라 크게 공간 색인을 사용하는 조인 알고리즘과 공간 색인을 사용하지 않는 조인 알고리즘으로 나뉜다.
학위논문의 첫 번째 파트에서는 공간 색인을 사용하는 조인 알고리즘을 제안한다. 공간 색인을 사용하는 기존 공간 조인 알고리즘에서는 원공간 색인인 R 트리가 널리 사용되는데, 원공간 색인이란 원공간상에서 표현된 공간 객체를 색인하는 구조로, 이를 활용한 조인은 크기를 가지는 공간 객체를 다루기 때문에 정형적인 방법이 아닌 휴리스틱에 의존하는 단점을 가진다. 반면, 변환공간 색인은 원공간 상의 공간 객체를 변환공간 상의 크기가 없는 점 객체로 변환하여 색인한 후에 이들을 다루기 때문에, 이를 활용한 공간 조인은 상대적으로 단순하고 정형적인 방법을 사용하는 장점을 가진다. 그러나, 이 방법은 R 트리와 같이 원공간 객체를 색인하는 원공간 색인에는 적용될 수 없는 문제점을 가진다.
본 논문에서는 이 두 방법의 장점만을 취하는 새로운 방법을 제안한다. 즉, 변환공간 뷰 (transform-space view)라는 새로운 개념과 이를 사용한 공간 조인 알고리즘인 변환공간 뷰 조인 알고리즘 (transform-space view join algorithm)을 제안한다. 변환공간 뷰란 원공간 색인에 대한 가상의 변환공간 색인으로서, 이미 구축된 원공간 색인을 구조적으로 변경하지 않고 가상의 변환공간 색인으로 해석할 수 있게 한다. 변환공간 뷰 조인 알고리즘은 원공간 색인들을 변환공간 뷰를 통해 변환공간 상에서 조인하는 알고리즘이다.
변환공간 뷰 조인 알고리즘에서 디스크 페이지 액세스 순서는 공간 채움 곡선에 의해 결정되는데, 이는 조인 성능에 큰 영향을 미친다. 본 논문에서는 새로운 공간 채움 곡선인 적응형 행 기준 순서(adaptive row major order: ARM order)를 제안한다. 적응형 행 기준 순서는 주어진 버퍼 크기에 따라 디스크 페이지 액세스 순서를 적응적으로 조정하여 원패스 버퍼 크기와 디스크 액세스 횟수를 크게 줄인다. 여기서, 원패스 버퍼 크기란 한 페이지당 한번의 디스크 액세스를 보장하는 최소 버퍼 크기이다. 정형적인 분석과 실험을 통하여 적응형 행 기준 순서를 사용하는 변환공간 뷰 조인 알고리즘의 우수성을 보인다. 실험 결과, 다른 공간 채움 곡선을 사용하는 변환공간 뷰 조인 알고리즘과 비교하여 적응형 행 기준 순서는 원패스 버퍼 크기를 최대 21.3배까지 줄이고, 디스크 액세스 횟수를 최대 74.6%까지 줄인다. 또한, R 트리를 원공간에서 조인하는 알고리즘들과 비교하여 원패스 버퍼 크기를 최대 15.7배까지 줄이고, 디스크 액세스 횟수를 최대 65.3%까지 줄인다.
학위논문의 두 번째 파트에서는 공간 색인을 사용하지 않는 조인 알고리즘을 제안한다. 공간 색인을 사용하지 않는 기존 조인 알고리즘들은 원공간을 파티션들로 분할한 다음에 각 공간 객체와 겹치는 파티션들에 공간 객체들을 분배한 다음에, 서로 조인관계에 있는 파티션들을 서로 조인함으로써 공간 조인을 수행한다. 이때, 원공간 상의 공간 객체는 크기를 가지기 때문에 파티션들의 가장자리에 위치한 공간 객체들은 복수의 파티션들과 겹친다. 겹치는 공간 객체들을 여러 파티션들에 복제하는 경우에는 복제로 인하여 성능이 떨어지며, 중복된 조인 결과가 나타남에 따라 이를 제거하기 위한 부담으로 성능이 떨어진다. 복제를 피하기 위해 복잡한 파티션 구조를 사용하는 경우에는 파티션들간의 조인 관계가 복잡해져 성능이 떨어진다. 이와 같은 문제점들은 원공간상의 객체가 크기를 가지기 때문에 일어나는 문제들이다. 만약, 객체의 크기를 변환공간 상의 점 객체로 변환하여 없앤 다음에 조인을 처리한다면, 공간 색인을 사용하지 않는 기존 조인 알고리즘들의 문제점들을 모두 해결하는 조인 알고리즘을 개발할 수 있다.
본 논문에서는 이러한 문제점들을 해결하는 방법으로 변환공간 파티션(transform-space partition)이라는 개념과 변환공간 파티션 조인 알고리즘(transform-space partition join algorithm)을 제안한다. 변환공간 파티션 조인 알고리즘은 변환공간을 변환공간 파티션들로 분할한 다음에 서로 조인 관계에 있는 변환공간 파티션들을 서로 조인하는 알고리즘이다. 제안하는 알고리즘은 원공간 상의 크기를 가지는 공간 객체를 변환공간 상의 크기를 가지지 않는 점 객체로 별도의 추가비용 없이 변환 해석한 후에 변환된 점 객체들을 변환공간 파티션들에 분배하여 조인을 수행하기 때문에 1) 공간 객체들의 복제가 필요 없고, 2) 파티션들의 구조가 단순하여 성능이 향상되는 장점을 가진다. 다양한 실험을 수행한 결과, 제안하는 변환공간 파티션 조인은 기존 조인 알고리즘들과 비교하여 수행 시간 측면에서 20.5 ~ 38.0% 더 우수한 성능을 보인다.
정리하면, 본 학위논문에서는 변환공간 뷰와 변환공간 파티션이라는 새로운 개념을 제안하고 이를 통해 공간 조인을 처리하는 두 알고리즘들을 제안한다. 제안하는 개념들과 알고리즘들은 기존 조인 알고리즘들이 가지는 여러 문제들을 해결하며 성능을 향상시킨다. 이러한 연구 결과로 볼 때, 변환공간 뷰와 변환공간 파티션 개념은 여러 공간 질의 처리 알고리즘들이 변환공간에서 새롭게 개발되는데 도움을 줄 것으로 사료된다.
