Time-series data, which are a series of one-dimensional real numbers, have been studied in various database applications such as data mining and data warehousing. In this thesis, we first extend the traditional similarity search methods on one-dimensional time-series data to support a multidimensional data sequence (MDS), such as digital signals, audio, and video streams. We investigate the similarity search methods for generalized multidimensional sequences from a large database. To prune irrelevant sequences in a database with respect to a given query, we introduce correct and efficient similarity functions. Both data sequences and query sequences are partitioned into subsequences, and each of them is represented by a minimum bounding rectangle (MBR). The query processing is based upon these MBRs, instead of scanning data elements of entire sequences. The method is designed (1) to select candidate sequences in a database, and (2) to find the subsequences of a selected sequence, each of which falls under the given threshold. The latter is of special importance in the case of retrieving subsequences from large and complex sequences. By using it, we do not need to browse the whole of the selected sequence, but just browse the sub-streams to find a part we want.
Next, we investigate the similarity search methods for the specialized video domain using the concept of an MDS. A video clip, a sequence of video frames describing a particular event, is represented by an MDS which is partitioned into video segments considering temporal relationship among frames, and then similar segments of the clip are grouped into video clusters. We present the effective video segmentation and clustering algorithm that guarantees the clustering quality to such an extent that satisfies predefined conditions. Based on video segments and clusters generated by the algorithm, we define various similarity functions and present the effective similarity search methods to find relevant video segments from large video data sets. Extensive experiments on synthetic, as well as real data sequences generated from a collection of TV news, dramas, and documentary videos, show the soundness of the proposed method, compared to the existing methods.
연속된 일차원의 실수의 집합으로 표현되는 시계열 데이터 처리는 데이터 마이닝과 데이터 웨어하우싱 등의 다양한 데이터베이스 응용 분야에서 연구되어 왔다. 본 논문에서는 첫째, 기존의 일차원 시계열 데이터에 대한 유사성 기법들을 응용 발전시켜, 여러 가지 디지털 신호와 오디오 및 비디오 스트림과 같은 일반적인 다차원 데이터 시퀀스를 검색할 수 있는 검색 기법을 제안한다. 주어진 질의에 대하여 관계가 없는 시퀀스들을 데이터베이스로부터 제거하기 위하여 정확성이 보장되고 효율적인 유사성 함수를 정의하였다. 데이터 시퀀스 및 질의 시퀀스는 서브 시퀀스로 분할되며, 각각의 서브 시퀀스는 최소 경계 사각형(MBR)으로 표현된다. 질의 처리는 시퀀스 내의 각 다차원 점들을 순차 검색하지 않고 최소 경계 사각형을 기초로 수행하여 효율을 높인다. 제안된 기법은 먼저 데이터베이스에서 후보 시퀀스 집합을 구한 후, 각 후보 시퀀스 내에서 주어진 질의 한계 값의 범위 안에 드는 부속 시퀀스들을 검출한다. 이러한 기법은 매우 방대하고 복잡한 시퀀스의 처리에 중요한 의미를 갖는다. 부속 시퀀스를 검출함으로써 후보 시퀀스 전체를 브라우징하지 않고 시퀀스 내의 원하는 구간 만을 확인하면 되기 때문이다.
다음으로, 본 논문에서는 일반적인 다차원 시퀀스의 유사성 검색 기법을 비디오 도메인에 초점을 맞추어 비디오 자료의 특성을 고려한 유사성 검색 기법을 제안하였다. 하나의 특정한 이벤트를 묘사하는 비디오 프레임들의 집합인 비디오 클립은 다차원 데이터 시퀀스로 표현되며, 프레임 간의 시간적 관계를 고려하여 비디오 세그먼트로 분할되고, 특성이 유사한 비디오 세그먼트들은 다시 비디오 클러스터로 군집화된다. 본 연구에서는 사전에 정의된 클러스터링 품질을 보장하는 비디오 세그멘테이션 및 클러스터링 알고리즘을 제안하고, 이 알고리즘에 의해 생성된 비디오 세그먼트 및 클러스터에 기초한 효과적인 유사성 검색 기법을 제안한다. 데이터베이스로부터 주어진 질의와 유사한 비디오 세그먼트들을 검색하기 위하여 세그먼트 및 클러스터 간의 거리 함수를 정의하였으며, 이 거리 함수에 의거하여 질의가 수행된다. 제안한 기법의 효과를 검증하기 위하여 TV 뉴스, 드라마, 다큐멘터리 영화 등의 실제 비디오 시퀀스 뿐만 아니라 가상으로 생성된 시퀀스에 대하여 제안된 기법을 평가하였다. 광범위한 실험들에 대한 결과는 기존의 기법에 비하여 본 논문에서 제시된 방법의 우수성을 보여주고 있다.