정적 공간 데이타베이스에서 페이지 순서화를 위한 비용 모델

조대수(DaeSoo Cho),홍봉희(BongHee Hong) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.3

지금까지 공간 데이타베이스에서 디스크 접근 비용을 줄이기 위해서 클러스터링에 대한 다양한 연구가 있었다. 클러스터링에 대한 연구는 크게 두 가지로 나뉜다. 첫째, 디스크 접근 횟수를 줄이기 위해서 함께 접근될 확률이 높은 공간 객체들을 동일한 페이지(또는 다중-페이지 클러스터)에 저장하기 위한 연구가 있다. 둘째, 디스크 탐색 시간을 줄이기 위해서 2차원상의 모든 페이지를 1차원적인 디스크상에 연속적으로 저장하기 위한 페이지 순서화에 대한 연구가 있다. 그런데, 페이지 순서화에 대한 기존의 연구에서는 공간 채우기 곡선(특히, Hilbert 곡선)만을 이용하고 있다. 공간 채우기 곡선을 이용한 순서화 방법은 공간 객체의 분포와 공간 질의의 유형과는 무관하게 순서가 생성되는 문제점을 갖는다. 이 논문에서는 디스크 탐색 비용을 최소화하기 위한 페이지 순서화 방법을 제시하고, 성능 평가 실험을 통해 제시한 페이지 순서화 방법이 기존의 방법에 비해 우수한 성능을 가짐을 입증한다. 이 논문이 공간 데이타베이스 분야에 가장 크게 기여한 부분은 최적의 페이지 순서를 결정하기 위해서 각각의 페이지 순서에 대해서 공간 질의(이 논문에서는 영역 질의를 대상으로 함)를 수행 하는데 필요한 디스크 탐색 횟수를 예측할 수 있는 비용 모델을 수식으로 제시한 것이다. Abstract A number of algorithms of clustering spatial data for diminishing the number of disk seeks required to process spatial queries have been developed. There have been two approaches to clustering spatial data: object clustering and page ordering. Object clustering is to store spatially adjacent objects at the same pages(or multi-page cluster) to reduce the number of page accesses. Page ordering is concerned with the order of pages in one-dimensional storage for storing two-dimensional spatial data to reduce the number of disk seeks. Previous works related to page ordering have only used the space filling curves, especially the hilbert curves. Page ordering based on the space filling curves does not take into account the uneven distribution of spatial objects and the types of spatial queries. In this paper we develop a cost model to define the page ordering problem based on performance measurement and then find out the method of page ordering for processing region queries in static databases. We make use of the method of simulated annealing as an optimization heuristic. The experimental results demonstrate that the newly proposed ordering method can achieve considerable improvement in its performance. The main contribution of this work is the cost model of the page order, from which we could estimate the number of disk seeks for processing region queries.

객체 지향 GIS DB를 위한 GSQL의 설계 및 구현

조대수(Cho DaeSoo),최진오(Choi JinOh),류우석(Ryu WooSeok),안경환(An KyoungHwan),홍봉희(Hong BongHee) 한국정보과학회 데이터베이스 소사이어티 1998 데이타베이스 연구 Vol.13 No.4

Threaded Quadtree : 이웃 검색을 위한 효율적인 색인 구조

조대수(Cho Daesoo),최진오(Choi Jinoh),홍봉희(Hong Bonghee) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

대용량의 데이타를 처리해야 하는 GIS는 사용자로부터의 공간 질의를 효율적으로 수행하기 위하여 공간 색인을 사용하고 있다. 기본 테이블의 공간 관련성을 기반으로 한 위상 연산이 필요한 질의를 추가의 위상 정보 없이 공간 색인만을 이용하여 처리하기 위해서는 공간 색인에 대해 위상 연산을 수행하기 위한 알고리즘이 필요하다. 이 논문에서는 quadtree를 공간 색인으로 사용할 때, 위상 연산을 수행하는데 기본이 되는 서로 인접한 노드의 검색을 효율적으로 처리하고자 한다. 이를 위하여 기존의 quadtree를 변형하지 않고, 대신에 말단 노드에서 사용하지 않고 있는 네 개의 NULL 포인터를 자신의 이웃을 가리키는 쓰레드로 사용하는 threaded quadtree를 제시하고, threaded quadtree의 분할, 병합시에 쓰레드를 관리하는 방법을 제시한다. 그리고 이를 이용하여 자신의 이웃을 효율적으로 검색하는 방법을 제시한다. 따라서 이 논문에서 제시하는 방법은 기존 quadtree에서 사용되던 모든 연산을 그대로 사용할 수 있으며, 추가적인 저장 장소의 낭비 없이 효율적으로 이웃 노드를 검색할 수 있는 장점일 가지고 있다.

고정 그리드 파일의 객체 및 셀 클러스터링 알고리즘

조대수(DaeSoo Cho),유진영(JinYoung Yoo),홍봉희(BongHee Hong) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.1

공간 데이타베이스에서 효율적으로 공간 질의를 처리하기 위해서는 클러스터링을 통해서 디스크 접근 비용을 줄이는 것이 필요하다. 이 논문은 공간 지역성에 기반을 둔 여러 가지 클러스터링 알고리즘을 제안하고 실험을 통해 제안한 클러스터링 알고리즘의 성능을 평가하였다. 이 논문에서 제안하는 클러스터링 알고리즘은 객체 클러스터링 알고리즘과 셀 클러스터링 알고리즘으로 나뉜다. 객체 클러스터링 알고리즘은 정규 분할 공간 색인 구조에서 영역 분할 선과 겹치는 객체들의 저장 위치를 결정하는데 사용 된다. 셀 클러스터링 알고리즘은 클러스터를 만들기 위해 정규 분할된 영역들을 그룹화하는데 사용된다. 실험 결과 객체 클러스터링 알고리즘에서는 객체간의 거리를 이용한 경우에 대체로 좋은 성능을 보였지만, 버퍼 크기가 커지거나 데이타가 희박한 영역의 질의에 있어서는 알고리즘 별로 성능의 차이는 거의 없었다. 셀 클러스터링 알고리즘에 대한 실험에서는 이 논문에서 제안한 클러스터링 알고리즘은 N-순서화 기법에 의한 클러스터링 알고리즘에 비해 우수한 성능을 보였다. 특히 중복 참조도를 이용한 경우와 셀의 무게 중심간 거리를 이용한 방법이 가장 우수하였다. For efficiently processing spatial queries in a spatial database, it is required to reduce the cost of disk accesses by clustering spatial data on one-dimensional space of disk. In this paper, we propose several clustering algorithms based on spatial locality in order to store spatial data in the fixed grid file, and evaluate the performance of each of newly proposed clustering algorithms. The clustering scheme consists of two steps: object clustering and cell clustering. The object clustering algorithms are used to determine to assign an object, which overlap with two or more adjacent grid-cells, to a specific grid cell. The cell clustering algorithms are used to make clusters by grouping a set of logically related grid-cells. Experimental results show that the object clustering algorithm using the object distance performs better than the others. However, if the buffer size becomes more larger and also the range queries are carried out in the sparse area, there is little difference in performance among the object clustering algorithms. The cell clustering algorithms proposed in this paper show better performance than the N-order-based clustering algorithm. In particular, the cell clustering algorithms using the number of duplicated references and the distance between the cell gravities are best.

복합 공간 객체의 모델링

조대수(Cho Daesoo),최진오(Choi Jinoh),홍봉희(Hong Bonghee) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.2A

GIS에서 공간 객체를 모델링할 때는 혼합(compound) 객체, 복합(complex) 객체를 정의하는 모델링 기능이 필요하다. 이 논문에서 새로 제시하는 복합 공간 객체 모델링 개념은 기존 복합 객체 개념을 확장하여 복합 공간 객체가 직접 기하 표현과 공간 연산자를 포함하는 것을 의미한다. 공간 객체의 그룹에 대한 공간 연산을 복합 공간 객체의 메소드로 모델링하는 방법을 설계한다.

효율적인 시공간 영역 질의 처리를 위한 궤적 색인의 노드 재배치 전략

임덕성(Duksung Lim),조대수(Daesoo Cho),홍봉희(Bonghee Hong) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.6

The trajectory preservation property that stores only one trajectory in a leaf node is the most important feature of an index structure, such as the TB-tree for retrieving object's moving paths in the spatio-temporal space. It performs well in trajectory-related queries such as navigational queries and combined queries. But, the MBR of non-leaf nodes in the TB-tree have large amounts of dead space because trajectory preservation is achieved at the sacrifice of the spatial locality of trajectories. As dead space increases, the overlap between nodes also increases, and, thus, the classical range query cost increases. We present a new split policy and entry relocation policies, which have no deterioration of the performance for trajectory-related queries, for improving the performance of range queries. To maximally reduce the dead space of a non-leaf node's MBR, the Maximal Area Reduction (MAR) policy is used as a split policy for non-leaf nodes. The entry relocation policy induces entries in non-leaf nodes to exchange each other for the purpose of reducing dead spaces in these nodes. We propose two algorithms for the entry relocation policy, and evaluate the performance studies of new algorithms comparing to the TB-tree under a varying set of spatio-temporal queries. TB-tree와 같이 시공간에서 궤적 검색을 위한 색인 구조는 단말 노드에 하나의 궤적만을 저장하는 궤적 보존의 특성을 가지기 때문에 궤적의 일부분을 추출하는 항해 질의(Navigational Query)에서 우수한 성능을 보인다. 그러나, 궤적 보존을 위해 공간적 지역성을 완전히 배제하는 구조를 가짐으로써 비단말 노드의 MBR(Minimum Bounding Rectangle)은 큰 사장 영역을 가지는 단점이 있다. 사장 영역 증가는 노드간의 중첩을 높이는 원인을 제공하기 때문에 영역 질의의 성능을 저하시키는 문제가 있다. 이 논문에서는 궤적 검색을 위한 색인 구조에서 항해질의 성능을 유지하면서 영역 질의의 성능을 향상 시키기 위한 비단말 노드 분할 정책과 엔트리 재배치 정책을 제시한다. 분할 정책은 비단말 노드의 분할 시 비단말 노드의 MBR을 최대한 감소시키는 최대 영역 축소(Maximal Area Reduction) 정책을 사용하고, 엔트리 재배치 정책은 비단말 노드를 구성하는 다수의 엔트리에서 MBR을 최대로 감소시킬 수 있는 엔트리의 위치를 재배치시키는 방법으로 이 논문에서는 분할 방법에 따라 2가지 재배치 전략을 제시하고 TB-tree와 성능을 비교한다.

클라이언트 변경 트랜잭션에서 공간 데이터의 동시성 및 일관성 제어

신영상(YoungSang Shin),최진오(JinOh Choi),조대수(DaeSoo Cho),홍봉희(BongHee Hong) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.2Ⅰ

서버의 공간 데이터가 클라이언트 캐쉬에 중복 저장되어 있는 클라이언트-서버 GIS 환경에서 동시에 수행될 수 있는 대화식 클라이언트 트랜잭션의 변경은 일관성 제어를 위해 서버와 다른 클라이언트에 전파되어야 한다. 이때 한 클라이언트의 캐쉬 변경이 다른 클라이언트의 변경과 출돌이 될 수 있는데, 클라이언트 트랜잭션은 기존의 기법으로는 동시성과 캐쉬 일관성이 제어 될 수 없다. 지도 수정 트랜잭션은 긴 트랜잭션이며 공간 관련성에 의한 종속성을 가지기 때문이다. 또한 캐쉬 변경 내용의 전파는 캐쉬 사용의 이점을 잃지 않기 위해 통신 부하 최소화 대책이 고려되어야 한다. 이 논문은 클라이언트-서버 GIS 환경에서 클라이언트 수정 트랜잭션의 동시성과 캐쉬 일관성 제어를 위하여 기존의 잠금 기법을 확장하고, 통신 부하의 최소화를 고려한 새로운 변경 전파 프로토콜을 설계하고 구현한 결과를 보인다.

모바일 환경을 위한 웹 지도 서비스의 확장 인터페이스

송관수(Kwansoo Song),고익준(Ikjun Ko),오병우(Byoungwoo oh),조대수(Daesoo Cho) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

최근 GIS는 여러 분야에서 다양하게 운용되고 있다. 최근에는 인터넷을 통한 정보 시스템의 요구가 급증하고 있으며, 웹 환경에서의 지리정보의 공유 및 활용방안에 대한 연구가 활발히 이루어지고 있다. 특히, 지리정보의 활용을 위해 웹 지도 서비스의 요구가 증대되고 있다. 이를 위해 OGC(Open GIS Consortium)에서는 WMS(Web Map Sevice) 명세를 제시하고 있다. 그러나, 현재 제시되고 있는 WMS 명세만으로는 최근 발전하고 있는 모바일 환경에서의 적용이 어렵기 때문에 WMS의 인터페이스의 확장이 필요하다. WMS 확장을 위해 본 논문에서는 기존의 WMS를 분석하고 이를 바탕으로 모바일 환경에 적합한 WMS 확장 인터페이스의 방안을 제시한다. 또한, 확장 인터페이스를 바탕으로 모바일 환경을 위한 WMS 구조를 설계하고 개발한다. 본 논문에서 제안하는 WMS의 확장 인터페이스 및 이를 기반으로 하는 WMS 구조는 사용자들의 요구에 적합한 WMS 개발에 기초 자료로 사용될 것으로 기대된다.

텔레매틱스를 위한 불확실성 기반의 이동체 색인

진희규(Heegyu Jin),김동현(Donghyun Kim),임덕성(Duksung Lim),조대수(Daesoo Cho),홍봉희(Bonghee Hong) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1B

속도와 방향이 바뀔 때 마다 이동체의 위치를 보고하는 TPR-tree는 이동체의 위치를 예측하는 오차가 적다. 그러나 긴 시간 간격으로 이동체의 위치를 보고하면 위치 예측의 불확실성이 높아져서 위치 예측의 오차 값이 증가한다. 불확실성이 높은 이동체를 TPR-tree에 적용할 때 이동체의 위치 정보를 갱신하기 위한 색인 검색 비용이 증가하고, 질의 결과의 정확도가 낮아지는 문제가 발생한다. 이 논문에서는 긴 시간 간격으로 이동체 위치를 보고할 때 발생하는 이동체 위치의 불확실성을 고려하기 위해서 불확실성 영역(uncertainty region)을 이용한 확장 TPR-tree를 제시한다. 불확실성이 높은 이동체의 위치 데이터를 처리하기 위해서 이동체의 이동 가능한 영역을 위치 예측의 오차 값을 이용하여 계산한 불확실성 영역을 설정하고, 검색을 위하여 노드의 BR을 계산할 때 불확실성 영역을 이용하여 BR을 확장한다.