이원성 기반 시계열 서브시퀀스 매칭의 인덱스 검색을 위한 최적의 기법

김상욱,박대현,이헌길,Kim, Sang-Wook,Park, Dae-Hyun,Lee, Heon-Gil 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.5

본 논문에서는 시계열 데이터베이스에서 서브시퀀스 매칭을 효과적으로 처리하는 방안에 관하여 논의한다. 먼저, 본 논문에서는 서브시퀀스 매칭을 위한 기존 기법의 인덱스 검색에서 발생하는 성능상의 문제점들을 지적하고, 이들을 해결할 수 있는 새로운 방법을 제시한다. 제안된 기법은 서브시퀀스 매칭의 인덱스 검색 문제를 윈도우-조인이라는 일종의 공간 조인 문제로 새롭게 해석하는 것에서 출발한다. 윈도우-조인의 빠른 처리를 위하여 제안된 기법에서는 서브시퀀스 매칭을 시작할 때 질의 시퀀스를 위한 R*-트리를 주기억장치 내에 구성한다. 또한, 제안된 기법은 데이터 시퀀스들을 위한 디스크 상의 R*-트리와 질의 시퀀스를 위한 주기억장치 상의 R*-트리를 효과적으로 조인할 수 있는 새로운 알고리즘을 포함한다. 이 알고리즘은 데이터 시퀀스들을 위한 R*-트리 페이지들을 인덱스 단계의 착오 채택 없이 단 한번만 디스크로부터 액세스하므로 디스크 액세스 측면에서 최적의 기법임이 증명된다. 또한, 다양한 실험을 통한 성능 평가를 통하여 제안된 기법의 우수성을 정량적으로 규명한다. In this paper, we address efficient processing of subsequence matching in time-series databases. We first point out the performance problems occurring in the index searching of a prior method for subsequence matching. Then, we propose a new method that resolves these problems. Our method starts with viewing the index searching of subsequence matching from a new angle, thereby regarding it as a kind of a spatial-join called a window-join. For speeding up the window-join, our method builds an R*-tree in main memory for f query sequence at starting of sub-sequence matching. Our method also includes a novel algorithm for joining effectively one R*-tree in disk, which is for data sequences, and another R*-tree in main memory, which is for a query sequence. This algorithm accesses each R*-tree page built on data sequences exactly cure without incurring any index-level false alarms. Therefore, in terms of the number of disk accesses, the proposed algorithm proves to be optimal. Also, performance evaluation through extensive experiments shows the superiority of our method quantitatively.

XML 문서를 위한 권한 부여 기법

강정모(Kang Jung Mo),이헌길(Lee Heon Gil) 강원대학교 산업기술연구소 2001 産業技術硏究 Vol.21 No.1

An XML is an markup language which has been focused on the next generation Web programming language. It easily represents the complex structure of a document, and it is possible to provide the access control over each component of an XML document. An implicit authorization technique means that granting an authorization to a node has effect on granting the same implicit authorization to its all descendants. Therefore, it enhances the time for the authorization grant and reduces the memory required for the authorization information. An authorization technique using an intention type and a authorization replacement solves a redundancy problem and decides whether the access is possible or the authorization conflict occurs at the first attempt.

시퀀스 데이터베이스에서 타임 워핑을 지원하는 효과적인 인덱스 기반 서브시퀀스 매칭

박상현,김상욱,조준서,이헌길,Park, Sang-Hyeon,Kim, Sang-Uk,Jo, Jun-Seo,Lee, Heon-Gil 한국정보처리학회 2002 정보처리학회논문지D Vol.9 No.2

본 논문에서는 대용량 시퀀스 데이터베이스에 타임 워핑을 지원하는 인덱스 기반 서브시퀀스 매칭에 관하여 논의한다. 타임 워핑은 시퀀스의 길이가 서로 다른 경우에도 유사한 패턴을 갖는 시퀀스들을 찾을 수 있도록 해준다. 최근의 연구에서 타임 워핑을 지원하는 효과적인 전체 매칭 기법을 제안된바 있다. 이 기법은 데이터 시퀀스들로부터 타임 워핑에 영향을 받지 않는 특징 벡터들의 집합을 대상으로 인덱스를 구성한다. 또한, 특징 공간상에서의 필터링을 위하여 삼각형 부등식을 만족하는 타임 워핑 거리의 하한 함수를 사용한다. 본 연구에서는 이 기존의 연구에 슬라이딩 윈도우를 기반으로 하는 접두어-질의 방법을 결합하는 새로운 기법을 제안한다. 인덱싱을 위하여 각 슬라이딩 윈도우와 대응되는 서브 시퀀스로부터 특징 벡터를 추출하고, 이 특징 벡터를 인덱싱 애트리뷰트로 사용하는 다차원 인덱스를 구성한다. 질의 처리를 위하여, 조건을 만족하는 질의 접두어들에 대한 특징 벡터들을 이용하여 다수의 인덱스 검색을 수행한다. 제안된 기법은 대용량의 데이터베이스에서도 효과적인 서브시퀀스 매칭을 지원한다. 본 연구에서는 제안된 기법이 착오 기각을 유발시키지 않음을 증명한다. 제안된 기법의 우수성을 규명하기 위하여 다양한 실험을 수행한다. 실험 결과에 따르면, 제안된 기법은 실제 S&P 500 주식 데이터와 대용량의 생성 데이터 모두에 대하여 큰 성능 개선 효과를 보이는 것으로 나타났다. This paper discuss an index-based subsequence matching that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. In earlier work, Kim et al. suggested an efficient method for whole matching under time warping. This method constructs a multidimensional index on a set of feature vectors, which are invariant to time warping, from data sequences. For filtering at feature space, it also applies a lower-bound function, which consistently underestimates the time warping distance as well as satisfies the triangular inequality. In this paper, we incorporate the prefix-querying approach based on sliding windows into the earlier approach. For indexing, we extract a feature vector from every subsequence inside a sliding window and construct a multidimensional index using a feature vector as indexing attributes. For query processing, we perform a series of index searches using the feature vectors of qualifying query prefixes. Our approach provides effective and scalable subsequence matching even with a large volume of a database. We also prove that our approach does not incur false dismissal. To verify the superiority of our approach, we perform extensive experiments. The results reveal that our approach achieves significant speedup with real-world S&P 500 stock data and with very large synthetic data.

윈도우 - 조인 : 이원성 기반 서브시퀀스 매칭을 위한 최적의 방법

김상욱(Sang-Wook Kim),박대현(Dae-Hyun Park),이헌길(Heon-Gil Lee),김만순(Man-Soon Kim),박정일(Jung-Il Park) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

본 논문에서는 시계열 데이터베이스에서 서브시퀀스 매칭을 효과적으로 처리하는 방안에 관하여 논의한다. 본 논문에서는 먼저, 기존의 이원성 기반 서브시퀀스 매칭 기법에서 발생하는 성능상의 문제점들을 지적하고, 이들을 해결할 수 있는 방법을 제시한다. 제안된 기법은 서브시퀀스 매칭 시 요구되는 인덱스 검색을 윈도우-조인이라는 일종의 공간 조인 문제로 새롭게 해석하는 것에서 출발한다. 제안된 기법에서는 효과적인 윈도우-조인의 처리를 위하여 질의 윈도우 점들을 위한 R*-트리를 주기억장치 내에 on-the-fly로 구성하는 방법을 사용한다. 또한, 데이터 윈도우 점들을 위한 디스크 상의 R*-트리 질의 윈도우 점들을 위한 주기억장치 상의 R*-트리를 효과적으로 조인할 수 있는 새로운 알고리즘을 제안한다. 제안된 기법은 R*-트리 페이지들을 착오 채택 없이 단 한번만 디스크로부터 액세스하므로 디스크 액세스 측면에서 이원성 기반 서브시퀀스 매칭을 위한 최적의 기법이다.

XML 문서를 위한 권한 부여 기법

강정모,이헌길 江原大學校 産業技術硏究所 2001 産業技術硏究 Vol.21 No.A

An XML is an markup language which has been focused on the next generation Web programming language. It easily represents the complex structure of a document, and it is possible to provide the access control over each component of an XML document. An implicit authorization technique means that granting an authorization to a node has effect on granting the same implicit authorization to its all descendants. Therefore, it enhances the time for the authorization grant and reduces the memory required for the authorization information. An authorization technique using an intention type and a authorization replacement solves a redundancy problem and decides whether the access is possible or the authorization conflict occurs at the first attempt.

비정규형 관계 모델을 바탕으로 한 설명 정보 데이타 모델

김준,이헌길,김진호 강원대학교 정보통신연구소 1997 정보통신논문지 Vol.1 No.-

As a result of recent advances in hardware and software technology, the processing requirements of multimedia data for end users have been increased. Because multimedia data have very large spaces, it takes a lot of time to access them. In order to retrieve multimedia data efficiently, the description of multimedia data has been used by several researches. This paper presents a new data model to represent the description of multimedia data conveniently. The data model is based on a Non-First Normal Form relational data model which supports atomic value, set, list, weighted-set, and weighted list as an attribute value by extending the existing relational data model. The data model will be more formal and practical than natural languages in representing the description of multimedia data, and it will be more powerful than the relational data modal. Therefore the data model will provide the description effectively to support the content-based retrieval of multimedia data.

이원성 기반 서브시퀸스 매칭을 위한 효율적인 방법

김상욱,박대현,이헌길 강원대학교 정보통신연구소 2002 정보통신논문지 Vol.6 No.-

In this paper, we discuss efficient processing of subsequence matching in time-series databases. We first point out the performance problems of Dual-Match, a previous subsequence matching method, and then propose a new one resolving them. The proposed method starts with a new attempt that observes the index search occurred in subsequence matching as a window-join, a kind of the spatial-join. For effective processing of the window-join, we build an R-tree for query window points within the main memory on the fly. We propose a novel algorithm for efficient processing of the join on the two R-trees; one for query window points residing in the main memory and the other for data window points residing in the disk. We also discuss the effectiveness of our approach over previous ones.