For efficient processing of spatial queries in spatial database systems, a spatial index that can maintain the clustering property is desirable since the queries are primarily processed against the spatial parts of the objects. A spatial database system can be used as the base of a geographic information system(GIS). Spatial access methods can be classified into the following four categories: space filling curves, object clipping or object duplication, region overlapping, and transformation. Among them, the transformation technique transforms objects in the original space into points in the higher- dimensional transform space using parameters that represent the shape of each object. The transformed points are then managed by a multidimensional point access method(PAM). It has been believed that transformation degrades the performance of spatial query processing since the transform space can not retain spatial proximity of the objects that are adjacently placed in the original space and thus does not preserve the clustering property.
In this dissertation, we show that this belief is incorrect and propose transformation-based algorithms for processing spatial queries. We first show that corner transformation, a variation of the transformation technique, provides the clustering property both for the index and the data file that stores the objects. This property enables corner transformation to be used as a clustering index in a spatial database system. We then propose spatial query processing algorithms based on corner transformation for spatial joins and other basic types of queries such as region queries, connected line segment queries. Main contributions of this dissertation are the following:
First, we propose algorithms based on corner transformation for processing spatial queries including spatial joins. In particular, we propose a transformation-based spatial join algorithm and show its excellence through analysis and experiments. In our knowledge, the transformation-based join algorithm 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 and the property of LRU buffering in order to reduce the number of disk accesses for spatial join. Experimental results show that the algorithm has better performance than the one using the R*-tree. The algorithm is applicable to all the spatial access methods using corner transformation.
Second, we discuss fundamental reasons why corner transformation preserves the clustering property. Corner transformation naturally places the objects having minimum bounding rectangles(MBR) of similar positions and sizes close together in the transform space. We also analyze how clustering conditions used in the R*-tree are reflected in corner transformation and then present necessary conditions that the multidimensional PAMs that manage the transformed objects should satisfy for better maintenance of the clustering property.
Third, we first explain the benefits of using an fixed-positioned object storage system for spatial database systems and then propose a mechanism that stores a new object into a page in the data file that contains a near object of the new object. This feature is necessary when corner transformation is used as a clustering index. A fixed-positioned object storage system is a system in which the positions of the objects never change.
Fourth, we propose the MBR-Multilevel Grid File(MBR-MLGF) as a PAM that satisfies the clustering conditions presented above and discuss its characteristics. We also propose a search mechanism to find the near object using the z-order, which reflects the characteristics of the cyclic splitting strategy of the MBR-MLGF. Through extensive experiments we compare the performance of the MBR-MLGF with that of the R*-tree. We conclude that corner transformation together with the MBR-MLGF preserves clustering by showing the MBR-MLGF has a performance similar to that of the R*-tree in normalized results of processing region queries.
Fifth, we improve the algorithm for constructing Octree-R, a data structure for ray tracing in rendering objects for three-dimensional GIS applications and present the result of analysis and experiments for its efficiency.
In summary, we have shown that corner transformation maintains the clustering property and thus can be used as clustering indexes in spatial database systems. Furthermore, we have proposed efficient algorithms based on corner transformation for spatial joins and other queries. Based on these results, we conclude that corner transformation is a practically useful category of spatial access methods for spatial database systems. We have developed a spatial object storage system GEOSS that integrates the MBR-MLGF as a spatial index in a multi-user general-purpose storage system KAOSS. We are now developing a new framework for geographic information systems by adding a spatial query language processor for an extended SQL incorporating spatial querying facilities. We believe this work provides a new insight into the whole new area of transformation-based spatial query processing.
공간 데이타베이스 시스템에서 공간 질의들을 효율적으로 지원하기 위해서는 클러스터링 성질을 유지하는 공간 액세스 방법을 이용하는 클러스터링 색인의 사용이 바람직하다. 이는 공간 질의들은 객체의 공간 데이타를 중심으로 하여 처리되기 때문이다. 공간 데이타베이스 시스템은 지리 정보 시스템(GIS) 등의 하부 구조로 사용되게 된다. 공간 액세스 방법들은 공간 순서화 기법, 객체 분할 또는 중복 기법, 영역 겹침 기법, 변환 기법의 네 부류로 나눌 수 있다. 이중에서 변환 기법은 원공간에서의 공간 객체의 특징을 대표할 수 있는 파라메터들을 사용하여 객체들을 원공간보다 높은 차원을 가지는 변환공간내의 점 객체로 표현하고 변환된 객체들을 다차원의 점 액세스 방법(point access method: PAM)을 이용하여 관리하는 기법이다. 변환 기법은 원공간에서 인접한 객체를 변환 공간에서 인접하지 않은 곳에 위치시켜서 즉, 클러스터링 성질을 유지하지 못하여 공간 질의 처리의 효율성을 저하시킨다고 알려져 왔다.
본 논문에서는 이러한 믿음이 옳지 않음을 보이고 변환 기법 기반의 여러 공간 질의 처리 알고리즘을 제안한다. 우리는 먼저 변환 기법의 일종인 구석점 변환 기법이 색인과 객체가 저장되는 데이타 화일의 두 부분 모두에 클러스터링 성질을 유지하게 함을 논한다.이 성질을 이용하면 구석점 변환 기법은 공간 데이타베이스 시스템의 클러스터링 색인으로 이용될 수 있다. 그리고 구석점 변환 기법을 이용한 공간 조인과 영역 질의, 연결 선분 질의 등의 기본 유형의 공간 질의에 대한 공간 질의 처리 알고리즘들을 제안한다. 다음은 본 논문에서 연구된 주요 내용들이다.
첫째, 구석점 변환 기법을 이용하는 공간 조인을 포함한 공간 질의 처리 알고리즘들을 제안한다. 특히 변환 기법 기반의 효율적인 공간조인 알고리즘을 제안하고 그 우수성을 분석과 실험을 통하여 입증한다. 우리가 알기로는 변환 기법을 이용하는 공간 조인 처리 알고리즘은 아직까지 제안된 바 없다. 제안된 알고리즘은 구석점 변환 기법에는 한 화일의 변환 공간 내에서 인접한 영역들에 대한 상대방 화일의 조인 대상 영역들이 많은 공통 부분을 가지는 특성을 이용하여 LRU 버퍼링 하에서 페이지 액세스 횟수를 최소화하도록 고안되었다. 실험을 통한 성능 평가 결과 제안된 공간조인 알고리즘은 R*-tree를 이용한 알고리즘보다 우수한 성능을 가진다. 이 알고리즘은 구석점 변환기법을 이용하여 객체를 관리하는 모든 PAM에 적용할 수 있다.
둘째, 구석점 변환 기법이 클러스터링 성질을 가지는 근본적인 이유를 논한다. 구석점 변환 기법은 유사한 위치와 크기의 최소 포함 사각형(minimum bounding rectangle: MBR)을 가지는 객체들을 변환공간의 인접한 부분에 자연적으로 위치시킨다. 또한 R*-tree에서 클러스터링을 위하여 사용한 기준들이 가지는 의미가 구석점 변환 기법에 어떠한 형태로 반영되었는 가에 대해서도 분석한다. 아울러 변환된 객체를 관리하는 점 액세스 방법이 보다 나은 클러스터링 성질을 가지게 하기 위하여 가져야 할 조건들을 제시한다.
셋째, 공간 데이타베이스 시스템에서 객체 위치고정 저장시스템을 하부 저장 구조로 사용할 경우의 장점을 설명하고, 구석점 변환 기법을 이러한 저장 시스템에서 클러스터링 색인으로 사용할 수 있도록 하기 위해서 삽입될 새로운 객체를 이 객체에 가까운 객체(near object)가 저장되어 있는 데이타 화일의 페이지에 저장하는 방법을 제안한다. 객체 위치고정 저장시스템은 저장된 객체의 위치를 변화시키지 않는 저장 시스템이다.
넷째, 위에서 제시된 변환 객체들을 관리하는 다차원 점 액세스 방법이 가져야 할 성질을 만족하는 다차원 PAM의 하나로 MBR-계층 그리드 화일(MBR-MLGF)을 제안하고 그 특성을 논한다. 또한 MBR-MLGF에서 사용하는 순환 분할 정책의 특성과 부합하는 공간 채움 곡선인 z-order를 이용하여 가까운 객체를 찾는 방법을 제안한다. 그리고 R*-tree와의 비교 실험을 통하여 MBR-MLGF가 정규화된 영역 질의 처리 결과에서 R*-tree와 유사한 성능을 가짐을 보임으로써 MBR-MLGF가 클러스터링 성질을 가짐을 논한다.
다섯째, 삼차원 GIS 응용을 위하여 삼차원 객체를 렌더링하는 데 있어서 광선 추적을 위한 데이타 구조인 Octree-R의 구성 알고리즘을 개선하고 그 효율성에 대한 분석 및 실험 결과를 제시한다.
이상의 연구 결과를 요약하면, 우리는 구석점 변환 기법이 클러스터링 성질을 가져서 공간 데이타베이스 시스템에서 클러스터링 색인으로 사용될 수 있음을 보였으며, 이를 이용한 공간 조인을 포함한 여러 공간 질의 처리를 위한 알고리즘들도 제안하였다. 이 결과를 토대로 구석점 변환 기법은 공간 데이타베이스 시스템에서 실제적으로 사용 가능한 액세스 방법의 한 부류라고 결론을 내릴 수 있다. 우리는 이 연구 결과를 바탕으로 하여 다사용자용 다목적 데이타 저장 시스템인 KAOSS에 MBR-MLGF를 통합한 공간 객체 저장 시스템 GEOSS를 개발한 바 있다. 그리고 이 시스템에 추가적으로 SQL을 확장한 공간 질의어를 위한 공간 질의어 처리기 등을 추가하여 지리 정보 시스템의 기본 프레임워크로 사용할 예정이다. 우리는 이 연구 결과가 변환 기법 기반의 공간 질의 처리 분야라는 새로운 분야에 대한 새로운 방향을 열어 주는 연구라 믿는다.
