$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

시계열 서브시퀀스 매칭을 위한 최적의 다중 인덱스 구성 방안

Optimal Construction of Multiple Indexes for Time-Series Subsequence Matching

초록

일정 기간 동안 객체의 변화한 값들을 기록한 것을 그 객체에 대한 시계열 데이타 시퀀스라고 부르며, 이들의 집합을 시계열 데이타베이스라고 한다. 서브시퀀스 매칭은 주어진 질의 시퀀스와 변화의 추세가 유사한 서브시퀀스들을 시계열 데이타베이스로부터 검색하는 연산이다. 본 논문에서는 서브시퀀스 매칭의 성능을 극대화하기 위한 방안을 제시한다. 먼저, 윈도우 크기 효과로 인한 서브시퀀스 매칭의 심각한 성능 저하 현상을 정량적으로 관찰하여, 하나의 윈도우 크기를 대상으로 만든 단 하나의 인덱스만을 이용하는 것은 실제 응용에서 만족할만한 성능을 제공할 수 없다는 것을 규명하였다 또한, 이러한 문제로 인해 다양한 윈도우 크기들을 기반으로 다수의 인덱스들을 구성하여 서브시퀀스 매칭을 수행하는 인덱스 보간법의 응용이 필요함을 보였다. 인덱스 보간법을 응용하여 서브시퀀스 매칭을 수행하기 위해서는 먼저 다수의 인덱스들을 위한 윈도우 크기들을 결정해야 한다. 본 연구에서는 물리적 데이타베이스 설계 방식을 이용하여 이러한 최적의 다수의 윈도우 크기들을 선정하는 문제를 해결하였다. 이를 위하여 시계열 데이터 베이스에서 수행될 예정인 질의 시퀀스들의 집합과 인덱스 구성의 기반이 되는 윈도우들의 크기의 집합이 주어질 때, 전체 서브시퀀스 매칭들을 수행하는 데에 소요되는 비용을 예측할 수 있는 공식을 산출하였다. 또한, 이 비용 공식을 이용하여 전체 서브시퀀스 매칭들의 성능을 극대화 할 수 있는 최적의 윈도우 크기들을 결정하는 알고리즘을 제안하였으며, 이 알고리즘의 최적성과 효율성을 이론적으로 규명하였다. 끝으로, 실제 주식 데이타와 대량의 합성 데이타를 이용한 실험 결과, 제안된 기법은 기존의 단순한 기법과 비교하여 1.5배에서 7.8배 성능이 향상됨을 보였다.

Abstract

A time-series database is a set of time-series data sequences, each of which is a list of changing values of the object in a given period of time. Subsequence matching is an operation that searches for such data subsequences whose changing patterns are similar to a query sequence from a time-series database. This paper addresses a performance issue of time-series subsequence matching. First, we quantitatively examine the performance degradation caused by the window size effect, and then show that the performance of subsequence matching with a single index is not satisfactory in real applications. We argue that index interpolation is fairly useful to resolve this problem. The index interpolation performs subsequence matching by selecting the most appropriate one from multiple indexes built on windows of their inherent sizes. For index interpolation, we first decide the sites of windows for multiple indexes to be built. In this paper, we solve the problem of selecting optimal window sizes in the perspective of physical database design. For this, given a set of query sequences to be peformed in a target time-series database and a set of window sizes for building multiple indexes, we devise a formula that estimates the cost of all the subsequence matchings. Based on this formula, we propose an algorithm that determines the optimal window sizes for maximizing the performance of entire subsequence matchings. We formally Prove the optimality as well as the effectiveness of the algorithm. Finally, we perform a series of extensive experiments with a real-life stock data set and a large volume of a synthetic data set. The results reveal that the proposed approach improves the previous one by 1.5 to 7.8 times.

참고문헌 (22)

  1. R. Agrawal, C. Faloutsos, and A. Swami, 'Efficient Similarity Search in Sequence Databases,' In Proc. Ini'l. Conf. on Foundations of Data Organization and Algorithms, FODO, pp. 69-84, Oct. 1993 
  2. R. Agrawal et al., 'Fast Similarity Seasch in the Presence of Noise, Scaling, and Translation in Time-Series Databases,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp. 490-501, Sept. 1995 
  3. C. Chatfield, The Analysis of Time-Series: An Introduction, 3rd Edition, Chapman and Hall, 1984 
  4. C. Faloutsos, M. Ranganathan, and Y. Manolopoulos, 'Fast Subsequence Matching in Time-series Databases,' In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp. 419-429, May 1994 
  5. Y. S. Moon, K. Y. Whang, and W. K. Loh, 'Duality-Based Subsequence Matching in Time-Series Databases,' In Proc. Int'l Conf. on Data Engineering, IEEE ICDE, pp. 263-272, 2001gineering, IEEE ICDE, pp. 263-272, 2001 
  6. Chen, M. S., Han, J., and Yu, P. S., 'Data Mining: An Overview from Database Perspective,' IEEE Trans. on Knowledge and Data Engineering, Vol. 8, No. 6, pp. 866-883, 1996 
  7. D. Rafiei and A. Mendelzon, 'Similarity-Based Queries for Time-Series Data,' In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp. 13-24, 1997 
  8. K. P. Chan and A. W. C. Fu, 'Efficient Time Series Matching by Wavelets,' In Proc. Int'l. Conf. on Data Engineering, IEEE ICDE, pp. 126-133, 1999 
  9. K. K. W. Chu, and M. H. Wong, 'Fast Time-Series Searching with Scaling and Shifting,' In Proc. Int'l. Symp. on Principles of Database Systems, ACM PODS, pp. 237-248, May 1999 
  10. D. Q. Goldin and P. C. Kanellakis, 'On Similarity Queries for Time-Series Data: Constraint Specification and Implementation,' In Proc. Int'l. Conf. on Principles and Practice of Constraint Programming, CP, pp. 137-153, Sept. 1995 
  11. D. Rafiei, 'On Similarity-Based Queries for Time Series Data,' In Proc. Int'l. Conf. on Data Engineering, IEEE ICDE, pp. 410-417, 1999 
  12. B. K. Yi and C. Faloutsos, 'Fast Time Sequence Indexing for Arbitrary $L_p$ Norms,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp. 385-394, 2000 
  13. D. J. Berndt and J. Clifford, 'Finding Patterns in Time Series: A Dynamic Programming Approach,' Advances in Knowledge Discovery and Data Mining, pp. 229-248, 1996 
  14. B. K. Yi, H. V. Jagadish, and C. Faloutsos, 'Efficient Retrieval of Similar Time Sequences Under Time Warping,' In Proc. Int'l. Conf. on Data Engineering, IEEE ICDE, pp. 201-208, 1998 
  15. S. H. Park et al., 'Efficient Searches for Similar Subsequences of Difference Lengths in Sequence Databases,' In Proc. Int'l. Conf. on Data Engineering, IEEE ICDE, pp. 23-32, 2000 
  16. S. W. Kim, S. H. Park, and W. W. Chu, 'An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases,' In Proc. Int'l. Conf. on Data Engineering, IEEE ICDE, pp. 607-614, 2001 
  17. N. Beckmann et al., 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,' In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp. 322-331, May 1990 
  18. W. K. Loh, S. W. Kim, and K. Y. Whang, 'Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases,' IEICE Trans. on Information and Systems, Vol. E84-D, No. 1, pp. 76-86, 2001 
  19. S. Berchtold, D. A. Keim, and H.-P. Kriegel, 'The X-tree: An Index Structure for High-Dimensional Data,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp. 28-39, 1996 
  20. R. Weber, H.-J. Schek, and S. Blott, 'A Quantitative Analysis and Performance Study for Similarity Search Methods in High-Dimensional Spaces,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp. 194-205, 1998 
  21. G. Das, D. Gunopulos, and H. Mannila, 'Finding Similar Time Series,' In Proc. European Symp. on Principles of Data Mining and Knowledge Discovery, PKDD, pp. 88-100, 1997 
  22. W. K. Loh, S. W. Kim, and K. Y. Whang, 'Index Interpolation: An Approach for Subsequence Matching Supporting Normalization Transform in Time-Series Databases,' In Proc. ACM Int'l. Conf. on Information and Knowledge Management, ACM CIKM, pp. 480-487, 2000 

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일