GEOSS 지리 정보 시스템을 위한 공간 객체 저장 시스템

송주원(Ju-Won Song),김상욱(Sang-Wook Kim),이영구(Young-Koo Lee),황규영(Kyu-Young Whang),홍의경(Eui-Kyeong Hong),김장수(Jang-Su Kim) 한국정보과학회 데이터베이스 소사이어티 1994 데이타베이스 연구 Vol.10 No.2

일차원 객체를 위한 구석점 변환 기법을 사용하는 새로운 공간 죠인 알고리즘

송주원(Ju-Won Song),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

공간죠인은 공간 데이타베이스 시스템에서 특정한 공간 관계를 가지는 객체쌍들을 찾기 위한 연산으로 그 처리 비용이 아주 크므로, 제공되는 공간 액세스 방법의 특성을 이용하는 효율적인 알고리즘이 연구되어야 한다. 본 논문에서는 일차원 원공간 객체를 위한 구석점 변환 기법을 이용하는 공간죠인 알고리즘을 제안하고 성능을 분석한다. 구석점 변환 기법에서는 한 화일의 인접한 두 영역에 대한 상대방 화일의 두 죠인 대상 영역은 서로 많은 공통 부분을 가진다. 제안된 알고리즘에서는 이 특성을 이용하여 공간죠인 처리에 필요한 디스크 액세스 횟수를 줄이는 전략을 사용한다. 제안된 알고리즘은 구석점 변환기법으로 객체를 색인하는 모든 액세스 방법에 적용 가능하다.

구석점 변환 기법을 이용한 연결선분 질의 처리

송주원(Ju-Won Song),황규영(Kyu-Young Whang) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.2Ⅰ

선분 객체로 표현되는 망 구조의 공간 데이타베이스에서 망 추적 등의 응용에 사용되는 질의인 연결선분 질의의 처리 방법은 지금까지 크게 연구된 적이 없다. 본 논문에서는 연결선분 질의를 구석점 변환 기법의 변환공간에서 처리하는 방법을 제안하고 원공간에서 영역 질의를 이용하여 처리하는 경우와 비교한 장점을 제시한다.

구석점 변환 기법을 이용한 공간 조인 알고리즘

송주원(Ju-Won Song),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang) 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.7

공간조인은 공간 데이타베이스 시스템에서 특징 공간 관계를 가지는 객체쌍들을 찾기 위한 연산이다. 공간조인은 처리 비용이 아주 큰 연산이므로, 제공되는 공간 액세스 방법의 특성을 충분히 이용하는 효율적인 알고리즘이 연구되어야 한다. 본 논문에서는 구석점 변환 기법을 이용한 공간조인 알고리즘을 제안하고, 분석과 실험을 통하여 그 우수성을 입증한다. 우리들이 아는 바로는 변환 기법을 이용한 공간조인 알고리즘은 아직 연구된 바 없다. 구석점 변환 기법에서는 한 화일의 인접한 두 영역에 대한 상대방 화일의 두 조인 대상 영역은 많은 공통 부분을 가진다. 제안된 알고리즘에서는 이러한 특성을 이용하여 공간 조인 처리에 필요한 디스크 액세스 횟수를 줄인다. 실험 결과 제안된 알고리즘은 Brinkhoff 등이 제안한 R* -tree를 이용한 알고리즘보다 일반적으로 나은 성능을 가진다. 이는 구석점 변환 기법이 공간 액세스 방법의 우수한 한 부류이며 공간 질의가 원공간보다 변환 공간에서 더 잘 처리될 수 있다는 좋은 징표라 할 수 있다. 이는 변환 기법이 클리스터링 성질을 유지 못한다는 일반적인 믿음은 뒤엎는 결과이다. 우리는 이 결과가 공간 질의에 대한 변환 공간 기반 처리라는 새로운 방향을 제시한다고 믿는다. Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database system Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through analysis and experiments. To the extent of authors' knowledge, the spatial join algorithm using corner transformation 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 in order to reduce the number of disk accesses for spatial join Experimental results show that the algorithm has a generally better performance than the R* tree based algorithm proposed by Brinkhoff et al. This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering We believe that our results will provide a new insight towards transformation based processing of spatial operations.

객체 변환 기법의 특성 분석

송주원(Ju-Won Song),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A

공간 데이타베이스시스템에서는 공간 질의를 효율적으로 지원하기 위하여 공간 색인 기법(spatialindexing techniques)을 사용한다. 공간 색인 기법은 공간 객체의 크기를 처리하는 메카니즘에 따라 영역 겹침 기법, 객체 분할 또는 중복 기법, 객체 변환 기법, 공간 순서화 기법 등으로 분류될 수 있다. 이 중 객체 변환 기법은 원 공간의 공간 객체의 특징을 대표할 수 있는 파라메터들을 사용하여 이 객체를 변환 공간내의 점 객체로 변환함으로써 객체를 저장하는 방법이다. 객체 변환 기법을 사용할 경우의 가장 큰 장점은 기존의 다차원 동적화일 구조를 그대로 사용할 수 있다는 점이다. 본 논문에서는 객체 변환 기법의 두 대표적 기법인 중앙점 변환 기법과 구석점 변환 기법에 대한 특성을 비교 분석한다. 그리고 이러한 특성을 이용한 공간 질의 처리 방법에 대하여 논한다.

공간 변환 기법에서의 클러스터링 성질

송주원(Ju-Won Song),김상욱(Sang-Wook Kim),이영구(Young-Koo Lee),황규영(Kyu-Young Whang),김장수(Jang-Su Kim) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.2A

공간 액세스 방법의 한 부류인 변환 기법은 별 뚜렷한 근거 없이 클러스터링 성질을 파괴한다고 믿어져 왔다. 그러나 본 논문에서는 변환 기법의 일종인 구석점 변환 기법이 클러스터링 성질을 자연스럽게 유지할 수 있는 특성을 가짐을 논한다. 그 근본적인 이유는 구석점 변환 기법이 최소 포함 사각형의 위치와 크기가 유사한 객체들에 대한 엔트리들을 같은 페이지에 위치시키기 때문이다. 또한 중앙점 변환 기법도 마찬가지로 클러스터링 성질을 자연스럽게 유지할 수 있는 특성을 가짐을 간단히 논한다.

공간 데이타베이스에서 구석점 변환 기법의 클러스터링 성질

송주원,이영구,김상욱,황규영(Ju Won Song),Young Koo Lee,Sang Wook Kim,Kyu Young Whang 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.8

Spatial access methods(SAM) are often used as clustering indexes in spatial database systems. Therefore, a SAM should have the clustering property in both the index and the data file. In this paper, we argue that comer transformation, which is a category of SAMs, naturally has the clustering property such that objects having minimum bounding rectangles of similar sizes and positions tend to be placed in the same page. Next, we show that corner transformation can be used as clustering indexes for storage systems with fixed object positions, and then introduce the MBR-MLGF as an example to implement such indexes. Extensive experiments comparing with the R*-tree show that corner transformation preserves the clustering property and therfore, it can be used as a very useful method for spatial query processing. 공간 액세스 방법은 일반적으로 공간 데이타베이스 시스템에서 클러스터링 색인으로 사용된다. 따라서 공간 액세스 방법은 색인과 데이타 화일에 대하여 동시에 클러스터링 성질을 가져야 한다. 본 논문에서는 공간 액세스 방법의 한 부류인 구석점 변환 기법이 최소 포함 사각형의 위치와 크기가 유사한 객체들에 대한 엔트리들을 같은 페이지에 위치시켜서 클러스터링 성질을 자연스럽게 유지함을 논한다. 또한 이 성질을 이용하면 구석점 변환 기법이 객체 위치고정 저장시스템에서 클러스터링 색인으로 사용될 수 있음을 보이고, 그 한 구현 방법으로 MBR-MLGF를 제시한다. 또한 R*-tree와의 비교 실험으로 구석점 변환 기법이 클러스터링 성질을 가짐을 보이고, 공간 질의 처리에 유용한 방법으로 사용될수 있음을 논한다.

계층 그리드 화일을 위한 일괄 구성 기법

김상욱(Sang-Wook Kim),송주원(Ju-Won Song),황규영(Kyu-Young Whang) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

계층 그리드 화일은 다중 애트리뷰트 액세스를 효과적으로 지원하는 다차원 동적 해쉬 화일 구조이다. 데이타베이스를 구축하는 경우에는 매우 방대한 양의 객체들을 대상으로 하므로 다차원 동적 화일의 효율적인 구성은 매우 중요하다. 본 논문에서는 계층 그리드 화일을 위한 일괄 구성 알고리즘을 제안한다. 제안된 일괄 구성 알고리즘에서는 계층 그리드 화일 구성에 필요한 각 페이지를 디스크로부터 한번 액세스할 때, 이곳에 저장될 모든 객체 혹은 엔트리들을 한꺼번에 처리하는 방식을 사용한다. 따라서 기존의 삽입 알고리즘을 반복적으로 적용함으로써 계층 그리드 화일을 구성하는 경우 같은 페이지를 디스크로부터 여러번 액세스하게 되는 오버헤드를 제거할 수 있다. 기존에 제안된 다차원 동적 화일을 위한 연산 알고리즘들은 주로 하나의 객체를 대상으로 하는 검색, 삽입, 삭제 알고리즘에 국한되어 왔으며, 이러한 일괄 구성에 관해서는 전혀 논의된 바 없다. 성능 평가를 위하여 본 알고리즘의 수행시 발생되는 디스크 액세스 수를 분석하였다. 분석 결과에 의하면, 일괄 구성을 위하여 반드시 요구되는 재배치 작업을 제외하면, 계층 그리드 화일의 구성을 위하여 사용되는 페이지 수 만큼의 디스크 쓰기가 발생하는 것으로 나타났다. 재배치 작업은 일괄 구성을 위한 필수적인 전처리 단계이므로 각 페이지당 한번의 디스크 액세스만을 요구하는 본 알고리즘은 일괄 구성을 위한 최적의 알고리즘이라 할 수 있다.

TRIE 구조를 이용한 한국어 전자 사전을 위한 데이타베이스 인덱스 구조

이승선(Seung-Sun Lee),송주원(Ju-Won Song),황규영(Kyu-Young Whang),최기선(Ki-Sun Choi) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.1

형태소 해석은 한국어 문서 처리의 중요한 요소중의 하나이다. 형태소 해석은 빈번한 사전 검색을 요하므로, 전자 사전은 한국어의 언어적 특성을 잘 반영하여 빠른 검색 속도를 제공하는 효율적인 색인 구조를 유지해야 한다. 본 논문에서는 트라이를 기본 구조로 하는 한국어 전자 사전을 위한 데이타 베이스 인덱스 구조(Compact TRIE Index:CompTI)를 설계하고 구현한다. 사전에 요구되는 주 기억 장치의 사용량을 최대한 줄이기 위하여, 색인 구조는 트라이 각 노드의 크기에 따라 분류된 유형 1, 유형 2, 유형 3 세가지의 배열을 사용한다. 또한, 빠른 사전 검색을 제공할 수 있도록 2400여개의 첫 글자를 위한 유형 0 배열을 따라 두고 다양한 기능을 부여한다. 이 데이타베이스 인덱스 구조의 특성은 다음과 같다. (1) 사전의 검색과 사전의 구성, 로드 및 저장이 기존의 다른 구조보다 훨씬 빠르다. (2) 색인 구조는 TRIE 구조에 필요한 최소의 주 기억 장치만을 사용한다. (3) 사전 엔트리의 삽입과 삭제가 가능하다.

CAD 데이타베이스를 위한 버젼 관리 시스템의 설계 및 구현

이해진(Hae-Jin Lee),송주원(Ju-Won Song),조완섭(Wan-Sup Cho),황규영(Kyu-Young Whang),유영욱(Young-Uk Yu),강길순(Gil-Soon Kang) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.3

컴퓨터를 이용한 설계(Computer-Aided Design CAD)는 엔지니어링 설계, VLSI칩 설계, 소프트웨어 공학 등의 분야에 널리 사용되고 있다. 최근에는 설계의 규모가 점차 커짐에 따라 설계의 복잡도가 점점 증가하게 되어 CAD 데이타 관리를 위한 설계자의 부담이 급격히 증가하게 되었다. 본 논문에서는 CAD 데이타 관리를 위한 네 가지 기본 요구사항인 CAD 객체의 모델링, CAD 데이타의 공유, 동적 참조, 변경 통보에 대하여 설명하고, 단일 사용자 환경에서 이들을 만족하는 버젼 관리 시스템(Version Management System : VMS)을 설계하고 구현하였다. VMS의 현저한 특징은 기존의 CAD 도구들을 소스 코드의 수정없이 통합할 수 있도록 CAD 도구들과 독립적으로 존재한다는 것이다. 본 논문에서는 이러한 독립적인 아키텍춰 하에서 네 가지 요구사항들을 충족시키기 위하여 해결해야하는 문제점들을 도출하고 이들을 해결하는 메카니즘들을 제안하였다. 특히, 동적 참조를 위하여 체크-인 및 체크-아웃 과정을 통하여 반-동적(semi-dynamic)으로 동적 참조를 실현하는 방법을 새로이 고안하였다. 또한, 설계자에게 CAD 데이타를 편리하게 관리할 수 있도록 하기 위하여 제공되는 새로운 연산인 콘피규레이션-체크-인, 콘피규레이션 체크-아웃, 작업 버젼 삭제, 릴리즈된 버젼 삭제 연산들의 의미(semantics)를 정의하고 VMS에 구현하였다. Computer-Aided Design(CAD) is used in various applications such as engineering design, VLSI chip design, and software engineering Recently, due to the complexity of the designs, the designer's burden for managing CAD data has been increasing very rapidly. In this paper, we first describe four requirements for managing CAD data : 1) modeling of CAD objects, 2) sharing of CAD data, 3) dynamic reference, and 4) change notification, and then, present the design of a version management system for single user environments, named VMS, that satisfies these requirements. The proposed architecture is independent of CAD tools, so that they can be integrated with VMS without modifying the source codes. We identify the problems involved with independent architectures and propose the mechanisms that solve them In particular, we propose a new mechanism that has the effect of dynamic reference in independent architectures. This effect is simulated semi-dynamically via check-in and check-out processes. We also propose new operations that are convenient for managing CAD data and define their semantics. They are configuration-check-in, configuration-check-out, working-version-deletion, and released-version-deletion operations.