의미 정보를 이용한 다차원 데이터 시퀀스의 유사성 척도 연구

이석룡,이주홍,전석주,Lee, Seok-Lyong,Lee, Ju-Hong,Chun, Seok-Ju 한국정보처리학회 2003 정보처리학회논문지D Vol.10 No.2

연속된 일차원 실수로 이루어진 시계열 데이터는 데이터 마이닝이나 데이터 웨어하우징과 같은 다양한 데이터베이스 응용 분야에서 연구되어져 왔다. 그러나 최근의 복잡한 비즈니스 환경에서, 다차원 데이터 시퀀스(multidimensional data sequence : MDS)는 일차원 시계열 데이터와 더불어 그 중요성이 더해가고 있다. 다차원 데이터 시퀀스의 예로써, 비디오 스트림은 색상과 질감 등의 속성들로 이루어진 다차원 공간상에서 MDS로 나타낼 수 있다. 본 논문에서는 패턴 유사성 검색에서 사용되는 효과적인 유사성 척도를 제시한다. 하나의 MDS는 여러 개의 세그먼트(segment)로 나누어지며, 각 세그먼트는 다양한 의미적인 특징들로 표현된다. 유사성 척도는 이러한 세그먼트에 대해서 정의되는데 이 척도를 사용하여 어떤 주어진 질의 시퀀스에 대하여 무관한 세그먼트들은 검색 대상에서 일차적으로 제외된다. 데이터 시퀀스와 질의 시퀀스 모두 세그먼트 단위로 분할되며, 질의 처리는 전체 시퀀스의 모든 데이터를 검색하지 않고 데이터 세그먼트와 질의 세그먼트의 특징을 비교하는 것을 기초로 하여 수행된다. One-dimensional time-series data have been studied in various database applications such as data mining and data warehousing. However, in the current complex business environment, multidimensional data sequences (MDS') become increasingly important in addition to one-dimensional time-series data. For example, a video stream can be modeled as an MDS in the multidimensional space with respect to color and texture attributes. In this paper, we propose the effective similarity measures on which the similar pattern retrieval is based. An MDS is partitioned into segments, each of which is represented by various geometric and semantic features. The similarity measures are defined on the basis of these segments. Using the measures, irrelevant segments are pruned from a database with respect to a given query. Both data sequences and query sequences are partitioned into segments, and the query processing is based upon the comparison of the features between data and query segments, instead of scanning all data elements of entire sequences.

비디오 검색 시스템을 위한 데이터 시퀀스 패턴 유사성 검색

이석룡,Lee Seok-Lyong 한국정보처리학회 2006 정보처리학회논문지D Vol.13 No.3

비디오 스트림은 다차원 공간에서 데이터 포인트의 시퀀스로 표현될 수 있다. 본 논문에서는 시퀀스 내의 데이터 포인트들의 값들의 근사치에 대한 정보와 시퀀스 내의 포인트들의 방향성에 대한 정보를 내포하고 있는 트랜드 벡터(trend vector)에 대한 소개와 이 벡터를 이용하여 데이터 시퀀스를 위한 유사 패턴 검색 기법을 제안한다. 시퀀스는 복수 개의 세그먼트로 분할되며 각 세그먼트는 트랜드 벡터로 표현된다. 질의처리는 시퀀스 내의 각각의 포인트들에 대하여 수행되는 대신, 트랜드 벡터들에 대하여 처리된다. 제안한 기법은 이 벡터를 사용하여 질의와 무관한 데이터 시퀀스들을 데이터베이스로부터 여과하고 질의 시퀀스와 유사한 시퀀스들을 검색하도록 설계되었다. 제안한 기법을 검증하기 위하여 비디오 스트림과 가상으로 생성된 데이터에 관하여 실험을 수행하였으며, 실험 결과 제안한 기법의 정밀도(precision)는 기존의 방법에 비하여 2.1배까지 향상되었으며 처리시간은 45%까지 감소되었음을 보여주고 있다. A video stream can be represented by a sequence of data points in a multidimensional space. In this paper, we introduce a trend vector that approximates values of data points in a sequence and represents the moving trend of points in the sequence, and present a pattern similarity matching method for data sequences using the trend vector. A sequence is partitioned into multiple segments, each of which is represented by a trend vector. The query processing is based on the comparison of these vectors instead of scanning data elements of entire sequences. Using the trend vector, our method is designed to filter out irrelevant sequences from a database and to find similar sequences with respect to a query. We have performed an extensive experiment on synthetic sequences as well as video streams. Experimental results show that the precision of our method is up to 2.1 times higher and the processing time is up to 45% reduced, compared with an existing method.

비디오 데이터 세트의 하이퍼 사각형 표현에 기초한 비디오 유사성 검색 알고리즘

이석룡,Lee, Seok-Lyong 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.4

이 연구에서는 대용량 비디오 데이터 스트림에 대한 유사성 검색 알고리즘을 제시한다. 수많은 프레임으로 이루어진 비디오 스트림은 각 프레임을 다차원 벡터(multidimensional vector)로 나타냄으로써 다차원 데이터 공간 상에서 시퀸스로 나타낼 수 있다. 이 시퀸스의 특성을 분석 함으로써 각 시퀸스를 비디오 세그먼트(video segment)와 이 세그먼트의 집합인 비디오 클러스터(video cluster)로 표현한다. 본 연구에서는 이러한 비디오 세그먼트와 클러스터를 사용하여 두 비디오 스트림 사이의 유사성 함수(similarity function)를 제시하고, 이 함수에 근거하여 비디오 세그먼트의 하이퍼 사각형과 대표 프레임에 기초한 두 가지의 유사성 검색 알고리즘을 제안한다. 전자는 정해성(correctness)을 보장하는 알고리즘이며, 후자는 정해성을 약간 희생하는 대신 상당한 효율성을 얻을 수 있는 알고리즘이다. 다양한 유형의 비디오 스트림 및 가상으로 생성된 스트림 데이터에 대한 실험을 통하여 제시한 알고리즘의 성능을 분석한다. In this research, the similarity search algorithms are provided for large video data streams. A video stream that consists of a number of frames can be expressed by a sequence in the multidimensional data space, by representing each frame with a multidimensional vector By analyzing various characteristics of the sequence, it is partitioned into multiple video segments and clusters which are represented by hyper-rectangles. Using the hyper-rectangles of video segments and clusters, similarity functions between two video streams are defined, and two similarity search algorithms are proposed based on the similarity functions algorithms by hyper-rectangles and by representative frames. The former is an algorithm that guarantees the correctness while the latter focuses on the efficiency with a slight sacrifice of the correctness Experiments on different types of video streams and synthetically generated stream data show the strength of our proposed algorithms.

대용량 비디오 데이터 세트를 위한 효율적인 비디오 클러스터링 및 검색 기법

이석룡(Seok-Lyong Lee),전석주(Seok-Ju Chun),정진완(Chin-Wan Chung) 한국정보과학회 데이터베이스 소사이어티 2003 데이타베이스 연구 Vol.19 No.3

VDCluster : 대용량 비디오 시퀀스를 위한 비디오 세그멘테이션 및 클러스터링 알고리즘

이석룡(Seok-Lyong Lee),이주홍(Ju-Hong Lee),김덕환(Doek-Hwan Kim),정진완(Chin-Wan Chung) 한국정보과학회 2002 정보과학회논문지 : 데이타베이스 Vol.29 No.3

본 논문에서는 비디오 저장이나 검색과 같은 비디오 정보 처리를 위한 중요한 기초 연구로써 비디오의 표현을 위한 효과적인 기법을 제안한다. 비디오 데이타 세트는 수초에서 수분 사이의 상연 시간을 갖는 비디오 클립들의 집합이며, 각 비디오 클립은 연속된 비디오 프레임들로 구성되어 있다. 이 비디오 클립은 다차원 데이타 시퀀스(multidimensional data sequence: MDS)로 표현될 수 있으며, 프레임 사이의 시간적인 정보를 고려하여 비디오 세그먼트로 나누어 지고, 한 클립 내에서 서로 유사한 세그먼트들은 다시 비디오 클러스터로 군집화된다. 따라서, 각 비디오 클립은 소수 개의 비디오 클러스터로 표현되어 진다. 본 논문에서 제안한 비디오 세그멘테이션 및 클러스터링 알고리즘 VDCLuster는 사전에 정의된 일정 수준의 클러스터링 품질을 보장하고 있으며, 다양한 비디오 시퀀스에 대한 실험을 통하여 알고리즘의 효과를 입증한다. In this paper, we investigate video representation techniques that are the foundational work for the subsequent video processing such as video storage and retrieval. A video data set is a collection of video clips, each of which is a sequence of video frames and is represented by a multidimensional data sequence (MDS). An MDS is partitioned into video segments considering temporal relationship among frames, and then similar segments of the clip are grouped into video clusters. Thus, the video clip is represented by a small number of video clusters. The video segmentation and clustering algorithm, VDCluster, proposed in this paper guarantee clustering quality to such an extent that satisfies predefined conditions. The experiments show that our algorithm performs very effectively with respect to various video data sets.

경향 벡터 기반 비디오 스트림 검색 시스템

이석룡(Seok-Lyong Lee),전석주(Seok-Ju Chun) 한국멀티미디어학회 2007 멀티미디어학회논문지 Vol.10 No.8

다차원 데이타 공간에서 시퀀스 데이타 세트를 위한 클러스터링 기법

이석룡(Seok-Lyong Lee),임동혁(Tong-Hyeok Lim),정진완(Chin-Wan Chung) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.4

비디오 스트림이나 음성 아날로그 신호와 같은 연속된 데이타는 특징 공간(feature space)에서 다차원 데이타 시퀀스(multidimensional data sequence)로 모델링될 수 있다. 본 논문에서는 이러한 다차원 데이타 시퀀스의 효과적인 클러스터링 기법에 대하여 연구한다. 각 시퀀스는 차후의 저장 및 유사성 검색 (similarity search)을 효율적으로 실행하기 위하여 소수 개의 하이퍼 사각형 (hyper-rectangle) 형태의 클러스터로 표현된다. 본 논문에서는 사전에 정의된 수준의 클러스터링 품질을 보장하는 선형 복잡도를 갖는 클러스터링 알고리즘을 제시하고, 다양한 비디오 데이타에 관한 실험을 통하여 알고리즘의 적합성을 보여준다. The continuous data such as video streams and voice analog signals can be modeled as multidimensional data sequences (MDS's) in the feature space. In this paper, we investigate the clustering technique for multidimensional data sequences. Each sequence is represented by a small number of hyper-rectangular clusters for subsequent storage and similarity search processing. We present a linear clustering algorithm that guarantees a predefined level of clustering quality, and show its effectiveness via experiments on various video data sets.

다차원 대용량 저밀도 데이타 큐브에 대한 고밀도 서브 큐브 추출 알고리즘

이석룡(Seok-Lyong Lee),전석주(Seok-Ju Chun),정진완(Chin-Wan Chung) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.4

데이타 웨어하우스는 기업이나 사회 전반에서 사용되는 방대한 데이타를 저장하고, 효율적인 분석을 가능하게 하는 데이타 저장소로써, 점점 그 활용도가 증가하고 있다. 본 연구에서는 이러한 데이타 웨어하우스 구축 기술의 핵심이 되는 다차원 데이타 큐브(multidimensional data cube) 기술을 연구하는데 목적이 있다. 고차원 데이타 큐브에는 필연적으로 내재하는 데이타의 희소성(sparsity)에 의한 검색 오버헤드가 있다. 본 연구에서는 이러한 오버헤드를 현격하게 감소시키는 알고리즘을 제시함으로써, 데이타 웨어하우스의 효율을 높이는 데 기여한다. 즉, 고차원의 희소 데이타 큐브에서 데이타가 조밀하게 밀집된 영역들을 찾아 그 영역을 중심으로 서브 큐브를 구축하여, 데이타 검색 시에 전체의 데이타 큐브를 대상으로 하지 않고 해당 서브 큐브 만으로 검색 대상을 제한시킴으로써 검색 효율을 높이는 알고리즘이다. 본 논문에서는 다차원 대용량의 희소 데이타 큐브로부터 밀도가 높은 서브 큐브를 찾기 위하여 비트맵과 히스토그램에 기반한 알고리즘을 제안하며, 실험을 통하여 제안한 알고리즘의 효용성을 보여준다. A data warehouse is a data repository that enables users to store large volume of data and to analyze it effectively. In this research, we investigate an algorithm to establish a multidimensional data cube which is a powerful analysis tool for the contents of data warehouses and databases. There exists an inevitable retrieval overhead in a multidimensional data cube due to the sparsity of the cube. In this paper, we propose a dense sub-cube extraction algorithm that identifies dense regions from a large sparse data cube and constructs the sub-cubes based on the dense regions found. It reduces the retrieval overhead remarkably by retrieving those small dense sub-cubes instead of scanning a large sparse cube. The algorithm utilizes the bitmap and histogram based techniques to extract dense sub-cubes from the data cube, and its effectiveness is demonstrated via an experiment.

SPEC : 데이타 웨어하우스를 위한 저장 공간 효율적인 큐브

전석주(Seok-Ju Chun),이석룡(Seok-Lyong Lee),강흠근(Heum-Geun Kang),정진완(Chin-Wan Chung) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.1

군집 질의는 사용자에 의해 명시된 질의 영역 내에서 큐브상의 군집 정보를 계산한다. 프리픽스-섬 기법에 기초한 기존의 방법들은 데이타의 누적된 합을 저장하기 위해 프리픽스-섬 큐브(PC)로 불리는 부가적인 큐브를 사용하므로 높은 저장공간 오버헤드를 초래한다. 이러한 저장공간 오버헤드는 기억장치의 추가적인 비용뿐만 아니라 업데이트의 부가적인 증식(propagation)과 더 많은 물리적 장치로의 접근시간을 유발시킨다. 본 논문에서는 대용량 데이타 웨어하우스에서 PC의 저장공간을 획기적으로 감소시킬 수 있는 ‘SPEC’으로 불리는 새로운 프리픽스-섬 큐브를 제안한다. SPEC은 PC내 셀들간의 종속에 의한 업데이트 증식을 감소시킨다. 이를 위해 대용량 데이타 큐브로부터 조밀한 서브큐브들을 발견하는 효과적인 알고리즘을 개발한다. 다양한 차원의 데이타 큐브와 여러가지 크기의 질의에 대해 폭 넓은 실험을 행하여 본 논문에서 제안한 방법의 효과와 성능을 조사한다. 실험적인 결과는 SPEC이 적절한 질의 성능을 유지하면서도 PC 저장공간을 상당히 감소시킴을 보여준다. An aggregation query computes aggregate information over a data cube in the query range specified by a user. Existing methods based on the prefix-sum approach use an additional cube called the prefix-sum cube(PC), to store the cumulative sums of data, causing a high space overhead. This space overhead not only leads to extra costs for storage devices, but also causes additional propagations of updates and longer access time on physical devices. In this paper, we propose a new prefix-sum cube called 'SPEC' which drastically reduces the space of the PC in a large data warehouse. The SPEC decreases the update propagation caused by the dependency between values in cells of the PC. We develop an effective algorithm which finds dense sub-cubes from a large data cube. We perform an extensive experiment with respect to various dimensions of the data cube and query sizes, and examine the effectiveness and performance of our proposed method. Experimental results show that the SPEC significantly reduces the space of the PC while maintaining a reasonable query performance.

A Feature Re-weighting Approach for the Non-Metric Feature Space

Robert Samuel Lee,김상희(Sang-Hee Kim),박호현(Ho-Hyun Park),이석룡(Seok-Lyong Lee),정진완(Chin-Wan Chung) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.4

이미지 데이타베이스 분야에 대한 다양한 기법들 가운데, 내용 기반 영상 검색 기법(Content Based Image Retrieval)은 대용량의 영상을 효율적으로 검색하고 탐색할 수 있도록 한다. 기존의 내용 기반 영상 검색 시스템은 사용자가 입력한 질의 이미지에서 낮은 레벨의 특성(low-level feature)을 추출하고 그에 기반하여 데이타베이스로부터 유사한 영상을 검색한다. 하지만 컴퓨터에서 사용하는 낮은 레벨의 특성은 실제 인간이 영상을 인식하는 방법과 다르게 영상을 인식한다는 단점이 있다. 이러한 단점을 보완하기 위하여 각 특성에 대한 가중치를 적합성 피드백(relevance feedback)을 통하여 재조정하는 기법이 개발되었다. 기존의 특성 가중치 조정(feature re-weighting) 기법은 모든 영상에 대하여 특성은 항상 고정된 길이의 벡터 데이타로 표현된다고 가정한다. 이러한 가정을 전제로 하여 기존의 기법은 특성 표현(feature representation)의 각 부분을 n차원 공간의 각 축에 할당한다. 하지만 특성 표현 기법의 발전에 따라 가변적인 길이의 벡터로 표현되는 특성이 출현하였으며, 이로 인하여 기존의 제한된 길이의 벡터로 표현되는 특성 표현에 기반한 특성 가중치 조정 기법의 유효성은 감소하게 되었다. 본 논문에서는 가변적인 크기의 벡터로 표현되는 특성에 대해서도 특성 가중치를 효과적으로 조정할 수 있는 기법을 제안한다. 본 기법은 특성에 기반하여 계산된 질의 영상과 데이타베이스 내부의 영상 간의 거리와 양방향 신뢰구간을 이용하여 특성 가중치를 조정한다. 이 때 각 특성의 거리 계산 방법에 대해서는 제한을 두지 않는다. 또한 각 특성의 표현에 있어서도 고정적인 크기 뿐만이 아니라 가변적인 크기의 데이타 역시 사용할 수 있도록 한다. 본 논문에서는 실험을 통하여 제안한 기법의 유효성을 입증하였으며, 다른 연구 결과와의 비교를 통하여 제안한 기법의 성능이 보다 우수함을 보였다. Among the approaches to image database management, content-based image retrieval (CBIR) is viewed as having the best support for effective searching and browsing of large digital image libraries. Typical CBIR systems allow a user to provide a query image, from which low-level features are extracted and used to find “similar” images in a database. However, there exists the semantic gap between human visual perception and low-level representations. An effective methodology for overcoming this semantic gap involves relevance feedback to perform feature re-weighting. Current approaches to feature re-weighting require the number of components for a feature representation to be the same for every image in consideration. Following this assumption, they map each component to an axis in the n-dimensional space, which we call the metric space; likewise the feature representation is stored in a fixed-length vector. However, with the emergence of features that do not have a fixed number of components in their representation, existing feature re-weighting approaches are invalidated. In this paper we propose a feature re-weighting technique that supports features regardless of whether or not they can be mapped into a metric space. Our approach analyses the feature distances calculated between the query image and the images in the database. Two-sided confidence intervals are used with the distances to obtain the information for feature re-weighting. There is no restriction on how the distances are calculated for each feature. This provides freedom for how feature representations are structured, i.e. there is no requirement for features to be represented in fixed-length vectors or metric space. Our experimental results show the effectiveness of our approach and in a comparison with other work, we can see how it outperforms previous work.