집합 값을 갖는 애트리뷰트에 대한 수직적으로 분할된 블록 중첩 루프 조인

황환규(Whang Whan Kyu) 강원대학교 산업기술연구소 2008 産業技術硏究 Vol.28 No.1

Set-valued attributes appear in many applications to model complex objects occurring in the real world. One of the most important operations on set-valued attributes is the set join, because it provides a various method to express complex queries. Currently proposed set join algorithms are based on block nested loop join in which inverted files are partitioned horizontally into blocks. Evaluating these joins are expensive because they generate intermediate partial results severely and finally obtain the final results after merging partial results. In this paper, we present an efficient processing of set join algorithm. We propose a new set join algorithm that vertically partitions inverted files into blocks, where each block fits in memory, and performs block nested loop join without producing intermediate results. Our experiments show that the vertical bitmap nested set join algorithm outperforms previously proposed set join algorithms.

공간 데이터베이스에서의 위상 - 방향 관계에 대한 추론

황환규(Whan-Kyu Whang),문현수(Hyun-Soo Moon),정호영(Ho-Young Jung) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.2Ⅰ

공간 관계는 공간 데이터베이스에서 질의 최적화를 위해 중요한 역할을 한다. 만일 공간 객체간의 공간 관계를 미리 알 수 있다면, 비용이 많이 드는 질의 처리는 피할 수 있다. 공간 데이터에 대한 공간 관계의 질의를 효과적으로 답하기 위해서는 각 공간 객체들의 공간 관계 파악이 중요하다. 그러나 방대한 양의 공간 데이터에 대하여 객체간의 모든 공간 관계를 저장한다는 것은 사실상 불가능하다. 이러한 문제를 해결하기 위해서는 자주 사용하는 공간 관계를 저장하고 자주 사용하지 않는 관계는 필요시 생성하는 것이 효율적이다. 본 논문에서는 공간 관계가 일부 주어졌을 때 주어진 공간 관계로부터 새로운 공간 관계를 추론하기 위한 공간 관계 추론 규칙을 제시하고자 한다.

이질형 분산 데이타베이스에서의 스키마 합성과 합성된 스키마에 대한 질의

황환규(Whan-Kyu Whang) 한국정보과학회 데이터베이스 소사이어티 1993 데이타베이스 연구 Vol.9 No.4

영역기반 이미지 검색을 위한 칼라 이미지 세그멘테이션

황환규(Whan-Kyu Whang) 대한전자공학회 2008 電子工學會論文誌-CI (Computer and Information) Vol.45 No.1

효율적인 저차원의 인덱싱을 제공하기 위해 이미지를 유사한 성질을 갖는 영역으로 나누고, 나누어진 영역에 대해 유사성을 비교하는 영역 기반 이미지 검색이 제안되었다. 그러나 영역 기반 이미지 검색은 이미지를 유사한 영역으로 나누기 위한 이미지 세그멘테이션 기술이 추가적으로 필요하다. 일반적인 칼라 자연 이미지의 경우 다양한 칼라와 질감 성분을 갖는 영역으로 나누는 것은 많은 어려움이 있다. 본 논문에서는 자동적인 칼라 이미지 세그멘테이션 알고리즘을 제안한다. 제안하는 세그멘테이션 방법은 양자화를 통해 칼라수를 줄이고 양자화 된 이미지를 Fisher의 클래스 선형 판별식을 이용하여 이미지의 전체적인 에지를 보여주는 그레이 레벨 이미지를 생성한다. 이렇게 얻은 그레이 레벨 에지 이미지를 지역적 임계치 비교를 통해 이진에지 이미지로 변환하고 이진 에지의 끊어진 부분을 찾아내어 인접 에지에 연결하여 영역을 생성한다. 마지막으로 나누어진 영역간의 유사성을 비교하고 유사한 영역을 병합하여 최종 세그멘테이션 결과 이미지를 생성한다. 본 논문에서는 세그멘테이션 알고리즘을 이용한 영역 기반 이미지 검색 시스템을 구현하였으며, 다양한 실험에 의하면 제안한 세그멘테이션 방법이 다양한 이미지에 대하여 양질의 세그멘테이션 결과를 보이는 것으로 나타났다. Region-based image retrieval techniques, which divide image into similar regions having similar characteristics and examine similarities among divided regions, were proposed to support an efficient low-dimensional color indexing scheme. However, color image segmentation techniques are required additionally. The problem of segmentation is difficult because of a large variety of color and texture. It is known to be difficult to identify image regions containing the same color-texture pattern in natural scenes. In this paper we propose an automatic color image segmentation algorithm. The colors in each image are first quantized to reduce the number of colors. The gray level of image representing the outline edge of image is constructed in terms of Fisher's multi-class linear discriminant on quantized images. The gray level of image is transformed into a binary edge image. The edge showing the outline of the binary edge image links to the nearest edge if disconnected. Finally, the final segmentation image is obtained by merging similar regions. In this paper we design and implement a region-based image retrieval system using the proposed segmentation. A variety of experiments show that the proposed segmentation scheme provides good segmentation results on a variety of images.

공간 질의 최적화를 위한 힐버트 공간 순서화에 따른 공간 분할

황환규,김현국,Whang, Whan-Kyu,Kim, Hyun-Guk 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.1

공간 질의 크기에 대한 근사치를 구하기 위해서는 입력 데이터 공간을 분할한 후 분할된 영역에 대하여 질의 결과 크기를 추정한다. 본 논문에서는 데이터 편재가 심한 공간 데이터에 대한 질의 크기 추정의 문제를 논의한다. 공간을 분할하는 기법으로 관계 데이터베이스에서 많이 사용되는 너비 균등, 높이 균등 히스토그램에 해당되는 면적 균등, 개수 균등 분할에 대한 방법을 검토하고 공간 인덱싱에 기초한 공간 분할방법에 대해서 알아본다. 본 논문에서는 공간 순서화 기법인 힐버트 공간 채움 곡선을 이용한 공간 분할을 제안한다. 제안한 방법과 기존의 방법을 실제 데이터와 인위 데이터를 사용하여 편재된 공간 데이터에 대한 질의 결과 크기의 추정에 대한 정확도를 비교한다. 본 실험에서 힐버트 채움 곡선에 의한 공간 분할이 공간 질의 크기 버켓 수의 변화, 데이터 위치 편재도의 변화, 데이터 크기의 변화에 대해서 기존의 분할 방법보다 질의 결과 크기 추정에 대해서 우수한 성능을 보였다. In order to approximate the spatial query result size we partition the input rectangles into subsets and estimate the query result size based on the partitioned spatial area. In this paper we examine query result size estimation in skewed data. We examine the existing spatial partitioning techniques such as equi-area and equi-count partitioning, which are analogous to the equi-width and equi-height histograms used in relational databases, and examine the other partitioning techniques based on spatial indexing. In this paper we propose a new spatial partitioning technique based on the Hilbert space filling curve. We present a detailed experimental evaluation comparing the proposed technique and the existing techniques using synthetic as well as real-life datasets. The experiments showed that the proposed partitioning technique based on the Hilbert space filling curve achieves better query result size estimation than the existing techniques for space query size, bucket numbers, skewed data, and spatial data size.

비트맵을 사용한 닫힌 빈발 시퀀스 마이닝

김형근,황환규,Kim Hyung-Geun,Whang Whan-Kyu 한국정보처리학회 2005 정보처리학회논문지D Vol.12 No.6

순차 패턴 탐사에 대한 연구는 대용량의 데이터베이스에서 사용자에 의해 주어지는 최소 지지도를 만족하는 빈발 시퀀스를 찾는 문제를 다룬다. 하지만 현재까지 이루어진 순차 패턴 탐사 방법은 빈발 시퀀스들의 길이가 길어지거나 최소 지지도가 상대적으로 낮게 주어진 상황에서는 생성되는 시퀀스가 기하급수적으로 많아져서 성능이 급격히 저하되는 문제점을 가지고 있다. 본 논문에서는 이 문제를 해결하기 위해서 모든 빈발 시퀀스의 정보를 포함하며 그 수가 현저히 적은 닫힌 빈발 시퀀스를 찾는 방법을 제안한다. 제안하는 알고리즘은 효율적으로 가지치기를 수행하기 위해서 깊이우선 탐색 방법으로 후보 시퀀스를 생성하고 데이터베이스를 비트맵으로 표현하여 비트 연산으로 지지도를 효율적으로 계산한다. 또한, 비트맵으로 표현된 시퀀스 특성을 이용하여 가지치기할 시퀀스를 적은 연산 비용으로 찾을 수 있다. 이런 장점을 통하여 제안한 방법이 지금까지 제안된 알고리즘보다 훨씬 빨리 닫힌 빈발 시퀀스를 찾는 것을 성능 실험을 통하여 확인하였다. Sequential pattern mining finds all of the frequent sequences satisfying a minimum support threshold in a large database. However, when mining long frequent sequences, or when using very low support thresholds, the performance of currently reported algorithms often degrades dramatically. In this paper, we propose a novel sequential pattern algorithm using only closed frequent sequences which are small subset of very large frequent sequences. Our algorithm generates the candidate sequences by depth-first search strategy in order to effectively prune. using bitmap representation of underlying databases, we can effectively calculate supports in terms of bit operations and prune sequences in much less time. Performance study shows that our algorithm outperforms the previous algorithms.

B⁺ 트리를 위한 벌크 로드

김상욱,황환규,Kim, Sang-Wook,Whang, Whan-Kyu 강원대학교 산업기술연구소 1995 産業技術硏究 Vol.15 No.-

In this paper, we propose a bulk-load algorithm for $B^+-trees$, the most widely used index structures in database systems. The main characteristic of our algorithm is to simultaneously process all the keys to be placed on each $B^+-trees$ page when accessing the page. This avoids the overhead for accessing the same page multiple times, which results from applying the $B^+-trees$ insertion algorithm repeatedly. For performance evaluation, we analyze our algorithm in terms of the number of disk accesses. The results show that the number of disk accesses excluding those in the redistribution process in identical to the number of $B^+-trees$ pages. Considering that the redistribution process is an unavoidable preprocessing step for bulk-loading, our algorithm requires just one disk access per $B^+-trees$ page, and therefore turns out to be optimal. We also present performance tendancy according to the changes of parameter values via simulation.

방향성 특징을 이용한 이미지 검색

정호영(Jung Ho Young),황환규(Whang Whan Kyu) 강원대학교 산업기술연구소 2000 産業技術硏究 Vol.20 No.1

For efficient massive image retrieval, an image retrieval requires that several important objectives are satisfied, namely: automated extraction of features, efficient indexing and effective retrieval. In this work, we present a technique for extracting the 4-dimension directional feature. By directional detail, we imply strong directional activity in the horizontal, vertical and diagonal direction present in region of the image texture. This directional information also present smoothness of region. The 4-dimension feature is only indexed in the 4-D space so that complex high-dimensional indexing can be avoided.

B+ 트리를 위한 벌크 로드 알고리즘

김상욱(Sang-Wook Kim),황환규(Whan-Kyu Whang),황규영(Kyu-Young Whang) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.2A

본 논문에서는 데이타베이스 인덱스 구조로 가장 널리 사용되는 B+ 트리를 위한 최적의 벌크 로드 알고리즘을 제안한다. 제안된 벌크 로드 알고리즘에서는 B+ 트리를 구성에 필요한 각 페이지를 디스크로부터 한번 액세스할 때, 이곳에 저장될 모든 키값들을 한꺼번에 처리하는 방식을 사용한다. 따라서 기존의 삽입 알고리즘을 반복적으로 적용함으로써 B+ 트리를 구성하는 경우 같은 페이지를 디스크로부터 여러번 액세스하게 되는 오버헤드를 제거할 수 있다. 성능 분석을 위하여 본 알고리즘의 수행시 발생되는 디스크 액세스 수를 분석하였다. 분석 결과에 의하면, 벌크 로드를 위하여 반드시 요구되는 재배치 작업을 제외하면, B+ 트리 구성에 사용되는 페이지 수 만큼의 디스크 쓰기가 발생하는 것으로 나타났다. 재배치 작업은 벌크 로드를 위한 필수적인 전처리 단계이므로 각 페이지당 한번의 디스크 액세스만을 요구하는 본 알고리즘을 벌크 로드를 위한 최적의 알고리즘이라 할 수 있다.

GIS에서 위상 관계의 유도와 일관성 검사

문현수(Hyun-Soo Moon),황환규(Whan-Kyu Whang),김상욱(Sang-Wook Kim) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1B

위상 관계는 공간 데이터베이스에서 질의 최적화를 위해 중요한 역할을 한다. 만일 공간 객체간의 위상 관계를 미리 알 수 있다면, 비용이 많이 드는 질의 처리는 피할 수 있다. 본 논문에서는 다음의 문제들을 다루려고 한다: 1) 공간 객체 사이에서 위상 관계, 2) 주어진 위상 관계들의 일관성 검사, 3) 주어진 위상 관계로부터 새로운 위상 관계의 유도 등이다. 이러한 동작들은 위상 관계와 연관된 질의들이 발생했을 때 효율적인 질의 처리를 위해 필요한 것이다. 특별히, 8가지 형태의 위상 관계(equal, disjoint, overlap, meets, contains, contained-in, properly-contains, and properly-contained-in)에 대해서 집중적으로 다루고자 한다. 그리고 위상 관계의 일관성을 검사하는 것과 주어진 위상 관계로부터 모든 가능한 관계들을 유도하는 것에 대한 알고리즘을 제시한다.