The shape of query windows for spatial selection queries is a rectangle in many cases. However, it can be issued for spatial selection queries with not only rectangular query widow, but also polygonal query window. Moreover, as the more spatial data the applications like GIS can manage, it can support the more various applications. Therefore it is valuable for considering about the refinement processing method suitable for not only rectangle, but also general polygonal query window.
It is the general state-of-the-art approach to use the plane-sweep algorithm for the computation algorithm in the refinement step as the spatial join queries, because the shape of spatial data and query window are all the general polygons. However, from the observation on the characteristics of spatial data and query windows, we can find in many cases that the shape of query window is much simpler than that of spatial data. Therefore there is something to be improved if we use the state-of-the-art approach, which is suitable for the two complex polygons, as the refinement processing strategy in this some situation.
From these observations, we suggest a new refinement process approach using PBST (Partition Based Sequential Testing) based on PEC (Partial Enclosed Circle) we developed. And we evaluated the performance of this new approach and the state-of-the-art approach by experiments with the real map data. From these experiments, we found that the new approach using PBST is more suitable than the other one as far as its query window is composed of up to 20 vertices. Although there is some deviation in the experimental result according to the characteristic of the real map data, if the number of vertices composing the query window is less than about 20, the new approach using PBST we suggest is superior to the state-of-the-art approach using Plane-Sweep by about 20% in the cases of small queries ranging about 1% which the most parts of spatial selection queries are issued in the real application.
도우로는 직사각형이 주로 사용된다. 하지만, 공간 선택 질의의 윈도우로는 직사각형이 아닌 일반적인 다각형 모양도 가능하다. 또한, 최근에는 GIS 등과 같은 응용 프로그램들이 성능 향상으로 인해 보다 많은 공간 데이터를 다룰 수 있게 됨에 따라, 여러 다양한 종류의 응용도 많이 등장하고 있다. 따라서, 직사각형뿐만 아니라 임의의 다각형 형태의 질의 윈도우에도 적합한 정제 단계 수행 전략에 대해 고려해 볼 필요가 있다. 이러한 전략으로는 질의 윈도우와 데이터가 모두 임의의 다각형이므로 기존의 공간 조인에서와 같이 plane-sweep 알고리즘을 이용하는 방법이 가장 일반적인 방법이다. 하지만, 공간 데이터와 질의 윈도우의 특성을 관찰해보면, 일반적으로 질의 윈도우가 공간 데이터보다 훨씬 간단한 모양으로 구성되어 있음을 알 수 있다. 하지만, 이 plane-sweep알고리즘은 두 대상이 모두 복잡한 임의의 다각형일 때 적합한 알고리즘이므로, 데이터에 비해 질의 윈도우가 훨씬 간단한 상황에는 개선의 여지가 있다.
따라서, 본 연구에서는 일반적인 다각형 형태의 공간 선택 질의를 위한 정제 단계 수행 방법으로서 PEC (Partial Enclosed Circle) approximation에 기반하는 PBST (Partition Based Sequential Testing) 방법을 제안하고 있으며, 기존의 방법과의 성능을 실세계에서 사용되는 지도 데이터를 이용해서 비교×평가하고 있다. 비록 실험에 사용되는 실제 지도 데이터의 특성에 따라 약간의 편차가 존재하지만, 일반적으로 볼 때 PBST를 사용하는 새로운 방법이, 질의 윈도우를 구성하는 점의 개수가 약 20개 이하인 경우에는, plane-sweep을 사용하는 기존의 방법보다 약 20% 정도의 성능 향상을 보이고 있음을 알 수 있다. 따라서 일반적인 다각형 형태의 질의 윈도우를 이용한 공간 선택 질의를 수행할 때, 사용되는 응용 프로그램이 약 20개 이하의 점으로 구성되는 질의 윈도우를 주로 사용하는 일반적인 경우라면, 기존의 방법보다는 본 논문에서 제시하는 PBST를 사용하는 방법이 보다 효과적이다.
