분산 지리정보시스템을 구현하는데 가장 어려운 점 중의 하나는 공간데이타베이스의 불일치이다. 특히, 여러 가지 이유로 발생하는 분산 공간 데이타베이스 사이의 위치 불일치는 공간 질의의 결과를 부정확하게 만든다. 하나의 간단한 해결책은 가장 중요한 사이트에 따라 각 사이트의 공간데이타베이스에 있는 위치 데이타를 보정하는 것이다. 그러나, 이러한 방법은 각 사이트의 자율성이 중시되어야 하는 경우에는 실용적이지 않다. 본 논문에서는 위치 데이타가 불일치하는 여러 개의 공간데이타베이스에 대하여 공간질의를 처리하는 방법을 제시한다. 본 논문에서 제시하는 방법은 각 지역 공간데이타베이스를 수정하지 않고 자율성을 보장하는 방식으로 공간질의를 처리할 수 있도록 한다. 본 논문에서 제안하는 방법은 탄성변형방법을 이용하면서, 각 질의의 위치를 동적으로 변환하는 방법에 기초하고 있다. 이 방법의 정확성은 수학적으로 증명이 되었으며, 실험으로도 확인하였다. 더욱이, 이 방법의 유용성 검증을 위하여 상용 데이타베이스시스템을 이용하여 구현하였다.
분산 지리정보시스템을 구현하는데 가장 어려운 점 중의 하나는 공간데이타베이스의 불일치이다. 특히, 여러 가지 이유로 발생하는 분산 공간 데이타베이스 사이의 위치 불일치는 공간 질의의 결과를 부정확하게 만든다. 하나의 간단한 해결책은 가장 중요한 사이트에 따라 각 사이트의 공간데이타베이스에 있는 위치 데이타를 보정하는 것이다. 그러나, 이러한 방법은 각 사이트의 자율성이 중시되어야 하는 경우에는 실용적이지 않다. 본 논문에서는 위치 데이타가 불일치하는 여러 개의 공간데이타베이스에 대하여 공간질의를 처리하는 방법을 제시한다. 본 논문에서 제시하는 방법은 각 지역 공간데이타베이스를 수정하지 않고 자율성을 보장하는 방식으로 공간질의를 처리할 수 있도록 한다. 본 논문에서 제안하는 방법은 탄성변형방법을 이용하면서, 각 질의의 위치를 동적으로 변환하는 방법에 기초하고 있다. 이 방법의 정확성은 수학적으로 증명이 되었으며, 실험으로도 확인하였다. 더욱이, 이 방법의 유용성 검증을 위하여 상용 데이타베이스시스템을 이용하여 구현하였다.
One of the most difficult problems in building a distributed GIS lies in the heterogeneity of spatial databases. In particular, positional mismatches between spatial databases, which arise due to several reasons, may incur incorrect query results. They result in unreliable outputs of query processin...
One of the most difficult problems in building a distributed GIS lies in the heterogeneity of spatial databases. In particular, positional mismatches between spatial databases, which arise due to several reasons, may incur incorrect query results. They result in unreliable outputs of query processing. One simple solution is to correct positional data in spatial databases at each site, according to the most accurate one. This solution is however not practical in cases where the autonomy of each database should be respected. In this paper, we propose a spatial query processing method without correcting positional data in each spatial database. Instead of correcting positional data, we dynamically transform a given query region or position onto each space where spatial objects of each site are located. Our proposed method is based on an elastic transformation method by using delaunay triangulation. Accuracy of this method is proved mathematically, and is confirmed by an experiment. Moreover, we implemented using common use database system for usefulness verification of this method.
One of the most difficult problems in building a distributed GIS lies in the heterogeneity of spatial databases. In particular, positional mismatches between spatial databases, which arise due to several reasons, may incur incorrect query results. They result in unreliable outputs of query processing. One simple solution is to correct positional data in spatial databases at each site, according to the most accurate one. This solution is however not practical in cases where the autonomy of each database should be respected. In this paper, we propose a spatial query processing method without correcting positional data in each spatial database. Instead of correcting positional data, we dynamically transform a given query region or position onto each space where spatial objects of each site are located. Our proposed method is based on an elastic transformation method by using delaunay triangulation. Accuracy of this method is proved mathematically, and is confirmed by an experiment. Moreover, we implemented using common use database system for usefulness verification of this method.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
하지만 [5]에서는 서로 대응하는 다각형의 모서리 수가 같으면 성립이 가능하나, 그 모서리의 수가 서로 다르면 [5] 에서제시하고 있는 방법으로는 객체의 위치가 보존된다는 것 올 보장할 수 없게 된다. 따라서, [기에서는 두 지도의 유사성 올 바탕으로 서로 대응되는 다각형의 유사성 비율을 [5]에서 사용한 0.7에서 그 값을 더 감소시켜 탄성변형 방법의 성능을 향상시키고자 하였다. 특히, [기에서는 기존의 연구들에서 제시되었던 탄성변형 기법과 다른 새로운 탄성변형 기법을 제시함으로써 지도상의 불일치를 보존한 후에도 지리 객체 사이의 위상 관계나 지리적 정확성 등이 보존된다는 것을 강조하고 있다.
따라서, 본 논문에서는 여러 개의 공간데이타베이스가 독립적으로 운영되고, 위치가 서로 불일치하는 경우 공간적 질의를 처리하는 방법올 제안한다.
예를 들어, 앞에서 제시한 탄성변형 방법에 의해 변형된 후에도 다각형의 면적이 변하지 않아야 한다는 것이다. 따라서, 본 논문에서는 이러한 제약 조건들올 만족시키기 위해서 들로니 삼각분할을 바탕으로 탄성변형을 이용한 불일치 보정방법을 제시하였다.
정보를 관리해야 한다. 따라서, 본 장에서는 공간질의 처리 기능을 구현하기 위하여 필요한 들로니 삼각형에 관한 정보를 관리할 수 있는 공간질의처리 시스템의 구조에 대해 살펴본다.
본 논문에서는 불일치 되는 공간데이타베이스 분산환경에서 주어진 질의를 올바르게 처리할 수 있도록 하는 방법을 제안하였다. 이 방법의 특징은 각각의 공간데이타베이스의 데이타를 바꾸지 않고 자율권을 보장하면서, 주어진 질의를 해당 데이타베이스에 맞게 변환하는 방식을 취하고 있다.
연합된 공간데이타베이스를 사용하기 위해서는 기능이나 형식적인 이질성뿐 아니라, 내용의 불일치도 함께해결되어져아 한다. 본 논문에서는 이와 같이, 위치 가서로 불일치되는 연합 공간데이타베이스에서의 질의처리 방법을 제안한다. 본 논문의 구성은 다음과 같다.
본 장에서는 4장예서 제시한 알고리듬의 정확성을 알아보기로 한다. 제시된 알고리듬의 정확성을 증명하기 위해서는 주어진 질의의 정확한 답을 알아야 한다.
이 방법에 의해 변형되어진 모양은 변형되기 전의 속성을 그대로 유지함으로써 불일치되는 부분들을 보정시키고자 하였다.
빨간색으로 표현되고 있다. 이와 같이 본 논문에서는 지형도나 지적도 전체를 변형시키는 과정을 생략하고, 공간데이타베이스에 주어지는 공간질의만을 변형 시켜 그 결과를 정확하게 얻고자 하는 것이다. 그림 13은 지적도와 지형도의 두 개의 공간데이타베이스에근접질의를 처리한 결과이다.
질의 영역을 보정하는 방법은 앞 절에서 설명한 들로니 삼각분할의 탄성변형을 이용한다. 특히, 질의영역 탄성변형 방법을 최근접 질의 처리방법과 포함 질의처리 방법에 적용하는 것을 제시한다. 다른 공간질의의 처리 방법도 이 두 가지 처리방법과 유사하므로 본 논문에서는 자세한 언급은 생략한다.
가설 설정
그러므로 본 논문에서는 알고리듬의 정확성을 증명하는 대신에 3장에서 설명한 개별 공간데이타베이스의 변형에 의한 기존의 방법과 본 논문에서 제시하는 질의영역의 변형에 의한 질의 결과가 동일하다는 것을 증명한다. 서로 다른 사이트에 있는 공간데이타베이스에서 하나의공간데이타베이스는 건물을 나타내는 지형도이고, 다른공간데이타베이스에는 교통도가 있다고 가정하자. 만일 각각의 공간데이타베이스에서 두 개의 도면이 서로 불일치 한다면, 사용자가 두 개의 도면에 공간질의를 주면 질의처리 결과는 서로 일관성을 보장할 수 없다.
제안 방법
제시하고 있다. [11]에서 제시한 방법은 수치지도 불일치 보정에 관한 연구로 불일치가 발생하는 기본 도와 설비 도의 시설물에 대해 들로니 삼각화를 이용한 유사도 비교를 통한 자동보정 방법을 제안하였다. 본 논문에서는 [11]에서 제시하고 있는 들로니 삼각분할올 이용한 탄성변형 방법을 사용한다.
그러면 공간질의영역의 탄성변형을 이용하여 최근접질의와 영역질의를 처리하는 방법을 살펴보기로 한다.
만약 어느 한쪽으로 공간데이타베이스를 변환한다면, 각 사이트의 자율성이 중시되어야 하는 경우에는 실용적이지 않으며, 공간데이타베이스에 있는 모든 데이타를 변환해야 하므로 그에 따른 비용이 매우 크다. 따라서 본 논문에서는 각 사이트의 공간데이타베이스를 변환하지 않고 공간질의를 변환하여 처리하였다. 공간질의를 변환함으로써 각 사이트의 공간데이타베이스는 자율성 올 보장할 수 있으며, 공간데이타베이스를 변환하는 것보다 훨씬 적은 비용이 따른다.
본 논문에서 제시하는 질의처리 방법의 가장 중요한 개념은 들로니 삼각분할올 이용한 질의영역의 변형이다. 따라서, 질의 영역을 변형하기 위해서는 기준점의 쌍의 집합이 유지되어야 하며, 그러기 위해서는 기준점 테이블이라는 것이 필요하다.
본 논문에서 제안하는 기본적 방법론은 들로니 삼각 분할을 이용한 탄성변형에 기초하고 있다. 따라서, 본 장에서는 들로니 삼각분할올 이용한 탄성변형 방법을 간단하게 소개한다[11].
[11]에서 제시한 방법은 수치지도 불일치 보정에 관한 연구로 불일치가 발생하는 기본 도와 설비 도의 시설물에 대해 들로니 삼각화를 이용한 유사도 비교를 통한 자동보정 방법을 제안하였다. 본 논문에서는 [11]에서 제시하고 있는 들로니 삼각분할올 이용한 탄성변형 방법을 사용한다. 자세한 내용은 다음 장에서 살펴보기로 한다.
본 몬문에서 제시한 방법의 유용성 검증을 위하여 5 장에서 설명한 정확성을 바탕으로 실험을 하였다. 실험환경은 펜티엄 4-2.
본 실험에서는 그림 13과 14에서 실행한 방법으로, 그림 15의 데이타를 상용 DBMS에 적용하여 공간질의의 변형 전과 변형 후를 비교하는 실험올 하였다. 그림 15는 부산의한 지역을 대상으로 한 데이타이다.
본 장에서는 위치가 일치하지 않는 공간데이타베이스시스템들이 있을 때, 질의 처리하는 방법을 제시한다. 특히, 앞의 방법에서 제시한 탄성변형방법과 달리, 본 논문에서 제시하는 방법의 기본적 개념은 각각의 공간데이타베이스를 수정하지 않고 주어잔 질의 영역이나 위치를 보정하여 각 시스템에서 공간질의를 수행하는 것이다.
특히, 공간데이타베이스를 주로 사용하며, 클라이언트/서버 구조의 다수 사용자 환경에 적 할 한 상용 DBMS인 ZEUS를 이용하여 구현하였다. 즉, 서로 다른 공간데이타베이스에 지형도와 지적도를 구축하여 공간질의를 처리하는 실험을 ZEUS 기반하에서 구현하였다. 물론, 공간질의에 대한 처리 결과는 변형 전의 공간질의와 변형 후의 공간질의가 동일하게 나타났다.
이 방법의 특징은 각각의 공간데이타베이스의 데이타를 바꾸지 않고 자율권을 보장하면서, 주어진 질의를 해당 데이타베이스에 맞게 변환하는 방식을 취하고 있다. 즉, 질의영역을 들로니 삼각 분할에 의한 탄성변형 방법을 이용하여 각각의 데이타베이스에맞게 변형하는 방법을 제안하였다.
4G와 512 메모리를 가진 윈도우 2000 환경이었으며, 실험은 Microsoft Visual C++을 사용하여 구현되었다. 특히, 공간데이타베이스를 주로 사용하며, 클라이언트/서버 구조의 다수 사용자 환경에 적 할 한 상용 DBMS인 ZEUS를 이용하여 구현하였다. 즉, 서로 다른 공간데이타베이스에 지형도와 지적도를 구축하여 공간질의를 처리하는 실험을 ZEUS 기반하에서 구현하였다.
대상 데이터
공간데이타베이스의 이질성은 공간데이타베이스 관리시스템의 이질성에서부터, 공간데이타모델의 이질성까지 다양하다. 본 논문에서 다루는 이질성은 공간데이타베이스의 위치 데이타 사이의 불일치에 따른 이질성이다.
이론/모형
공간 색인 방법에는 여러가지 방법이 제시되어 있다[15T 7]. 본 논문에서는 [16]을 토대로 보다 효과적인 클러스터링을 지원하기 위해 [15]에서 제안된 공간 색인 방법을 사용하여 공간 연산을 수행하도록 하였다. 위의 두 질의처리 방법의 성능은 각각의 공간데이타베이스 시스템의 질의처리 성능에 따라 결정된다.
특히, 앞의 방법에서 제시한 탄성변형방법과 달리, 본 논문에서 제시하는 방법의 기본적 개념은 각각의 공간데이타베이스를 수정하지 않고 주어잔 질의 영역이나 위치를 보정하여 각 시스템에서 공간질의를 수행하는 것이다. 질의 영역을 보정하는 방법은 앞 절에서 설명한 들로니 삼각분할의 탄성변형을 이용한다. 특히, 질의영역 탄성변형 방법을 최근접 질의 처리방법과 포함 질의처리 방법에 적용하는 것을 제시한다.
성능/효과
그러나 모든 공간데이타베이스에서 위치데이타는 오차를 포함하고 있고, 더욱이 불일치 하는 공간 데이타베이스가 있을 경우, 어느 것이 정확한지 알 수 없으므로, 주어진 질의의 '정확한 답을 알 수 없다. 그러므로 본 논문에서는 알고리듬의 정확성을 증명하는 대신에 3장에서 설명한 개별 공간데이타베이스의 변형에 의한 기존의 방법과 본 논문에서 제시하는 질의영역의 변형에 의한 질의 결과가 동일하다는 것을 증명한다. 서로 다른 사이트에 있는 공간데이타베이스에서 하나의공간데이타베이스는 건물을 나타내는 지형도이고, 다른공간데이타베이스에는 교통도가 있다고 가정하자.
표에서 알 수 있듯이 공간질의의 변형 전과 변형 후의 결과가 100%에 가깝도록 동일하게 나타났다. 따라서, 본 논문에서 제시한 방법이 실질적으로도 충분히 사용이 가능하다는 것을 입증해 준다.
물론, 질의영역을 변형하는 시간이 추가되지만 이는 주로 계산 시간이므로 각 데이타베이스의 질의처리 시간에 비하여 무시할 만큼 작은 시간이다. 따라서, 본 논문에서는 성능적인 측면은 고려하지 않고, 원래의 포함 질의와 변형된 포함질의가 각각 처리된 결과가 동일하면 공간질의 보정의 정확성을 입증한 것으로 만족한다.
먼저, 삼각형 단위로 이루어지는 각각의 탄성변형은 위상적인 특성을 보존한다. 이에 따라 삼각형 변형의 조합으로 이루어진 전체적인 탄성변형도 위상적인 특성 올 보존하게 된다.
물론, 공간질의에 대한 처리 결과는 변형 전의 공간질의와 변형 후의 공간질의가 동일하게 나타났다. 이 실험은 상용 데이타베이스 시스템을 사용함으로써 실질적으로도 사용이 가능하다는 것을 말해주고 있다. 다음 그림은 본 논문에서 사용한 실험 데이타로 지형도와 지적도의 일부분을 보여주고 있다.
제시된 알고리듬의 정확성을 증명하기 위해서는 주어진 질의의 정확한 답을 알아야 한다. 즉, 주어진 질의의 정확한 답을 알면 그것과 본 논문에서 제시하는 질의처리방법의 결과와 비교하여 정확성을 증명할 수 있다. 그러나 모든 공간데이타베이스에서 위치데이타는 오차를 포함하고 있고, 더욱이 불일치 하는 공간 데이타베이스가 있을 경우, 어느 것이 정확한지 알 수 없으므로, 주어진 질의의 '정확한 답을 알 수 없다.
후속연구
본 논문에서 제안하는 방법을 일반화시켜 이용하기 위해서는 본 논문의 방법에 필요한 들로니 삼각형에 관한 정보를 관리하는 방안올 만들어야 한다. 특히, 들로니 삼각형의 정보를 미들웨어가 관리하기 위한 여러 가지 표준이나 프로토콜등이 정의되어야 한다.
참고문헌 (18)
ISO/TC211/WG2 Report N298 ISO WD15046-20, Geographic information-spatial Operators, 1996
ISO/TC211/WG2 Report N298, Geospatial Data Models and Operators, 1996
Open GIS Consortium, The OpenGIS Abstract Specification, version 4, 1999
R. Laurini and D. Thompson, Fundamentals of Spatial Information Systems, 2nd edition, Academic Press, 1992
M. G. Cho, K. J. Li and H. G. Cho, 'A Rubber Sheeting Method With Polygon Morpging,' SDH, pp. 7A 31-42, 1996
S. Servigne, R. Laurini, 'Updating Geographic Databases Using Multi-Source Information,' ACMGIS, 1996
M. G. Cho and H. G. Cho, 'Resolving Mismatches and Measure Functions for Evaluating its Validity,' SDH, 2000
P. Langlois, Une transformation elastique du plan basee sur un modele d'interaction spatiale, Applications a la geomatique. Technical Paper in French, MTG, University of Rouen, 1994
P. Dufour, Les bases de donnees geographiques federees : continuities geometriques et topologiques, Memoire de DEA in French, INSA de Lyon, June 1995
Kurt Mehlhorn, Stefan Naher, Michael Seel' Christian Uhrig, The LEDA user Manual, Version 4.2
박상미, 정규상, 손은정, 이기준, '지리 정보 시스템용 수치 지도 자동 보정 기법', 한국정보과학회 97 가을 학술발표논문집, 제24권 제2호, 1997
K. Cheung, and A. Fu, 'Enhanced Nearest Neighbor Search on the R-tree,' Proc. ACM SIGMOD Record 27(3), pp.16-21, 1998
Roussopoulos N., Kelley S., Vincent F, 'Nearest Neighbor Queries,' Proc. ACM SIGMOD, pp.71-79, 1995
장인성, 이기준, '밀도를 이용한 k-최근접 탐색 방법', 한국정보학회 2000 가을 학술발표논문집, 제27권 제2호, 2000
N. Beckmann, H.P. Kriegel, R. Schneider, and B. Seeger, 'The R*-Tree, An Efficient and Robust Access Method for Points and Rectangles,' Proc. ACM SIGMOD, pp.322-331, 1990
A. Guttman, 'R-Tree, A dynamic Index Structure for Spatial Searching,' Proc. ACM SIGMOD, pp.47-57, 1984
J. Nievergelt, Hinterberger and KC.Sevick, 'The Grid File: An Adaptable, Symmetric Multikeys File Structure,' ACM Trans. Database Systems, 9(1), pp.38-71, 1984
※ AI-Helper는 부적절한 답변을 할 수 있습니다.