비디오 검색 시스템을 위한 데이터 시퀀스 패턴 유사성 검색
Pattern Similarity Retrieval of Data Sequences for Video Retrieval System
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
비디오 스트림은 다차원 공간에서 데이터 포인트의 시퀀스로 표현될 수 있다. 본 논문에서는 시퀀스 내의 데이터 포인트들의 값들의 근사치에 대한 정보와 시퀀스 내의 포인트들의 방향성에 대한 정보를 내포하고 있는 트랜드 벡터(trend vector)에 대한 소개와 이 벡터를 이용하여 데이터 시퀀스를 위한 유사 패턴 검색 기법을 제안한다. 시퀀스는 복수 개의 세그먼트로 분할되며 각 세그먼트는 트랜드 벡터로 표현된다. 질의 처리는 시퀀스 내의 각각의 포인트들에 대하여 수행되는 대신, 트랜드 벡터들에 대하여 처리된다. 제안한 기법은 이 벡터를 사용하여 질의와 무관한 데이터 시퀀스들을 데이터베이스로부터 여과하고 질의 시퀀스와 유사한 시퀀스들을 검색하도록 설계되었다. 제안한 기법을 검증하기 위하여 비디오 스트림과 가상으로 생성된 데이터에 관하여 실험을 수행하였으며, 실험 결과 제안한 기법의 정밀도(precision)는 기존의 방법에 비하여 2.1배까지 향상되었으며 처리시간은 45%까지 감소되었음을 보여주고 있다.
Abstract
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.
참고문헌 (20)
- R. Agrawal, "Efficient similarity search in sequence databases", pp.69~84 (1993)
- S. Berchtold, "The X-tree: an index structure for high-dimensional data", pp.28~39 (1996)
- N. Beckmann, "The R*-tree: an efficient and robust access method for points and rectangles", pp.322~331 (1990)
- C. Faloutsos, "A signature technique for similarity-based queries." (1997)
- C. Faloutsos, "Fast subsequence matching in time-series databases", pp.419~429 (1994)
- M. Flickner, "Query by image and video content : The QBIC system.", 28(9), pp.23~32 (1995)
- A. Guttman, "R-trees: a dynamic index structure for spatial searching", pp.47~57 (1984)
- H. V. Jagadish, "Linear clustering of objects with multiple attributes", pp.332~342 (1990)
- N. Katayama, "The SR-tree: an index structure for high-dimensional nearest neighbour queries", pp.369~380 (1997)
- E. Keogh, "Locally adaptive dimensionality reduction for indexing large time series databases.", pp.151~162 (2001)
- E. Keogh, "A probabilistic approach to fast pattern matching in time series databases.", pp.20~24 (1997)
- S. L. Lee, "Similarity search for multidimensional data sequences.", pp.599~608 (2000)
- S. L. Lee, "Hyper-rectangle based segmentation and clustering of large video data sets.", 141(1), pp.139~168 (2002)
- T. Pavlidis., "Waveform segmentation through functional approximation.", c-22(7) (1976)
- D. Rafiei, "On similarity queries for time series data.", pp.410~417 (1999)
- D. Rafiei, "Similarity-based queries for time series data.", pp.13~25 (1997)
- C. Wang, "Supporting content-based searches on time series via approximation." (2000)
- B. K. Yi, "Fast time sequence indexing for arbitrary Lp norms.", pp.385~394 (2000)
- 이석룡, "비디오 데이터 세트의 하이퍼 사각형 표현에 기초한 비디오 유사성 검색 알고리즘", 11(4), pp.823~834 (2004)
- 이석룡, "의미정보를 이용한 다차원 데이터 시퀀스의 유사성 척도 연구", 10(2), pp.283~292 (2003)