본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

시계열 데이터베이스에서 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭
A Single Index Approach for Subsequence Matching that Supports Normalization Transform in Time-Series Databases

문양세   (강원대학교 IT특성화대학 컴퓨터학부UU0000037  ); 김진호   (강원대학교 IT특성화대학 컴퓨터학부UU0000037  ); 노웅기   (한국과학기술원 전자전산학과/첨단정보기술연구센터UU0001375  );
  • 초록

    정규화 변환은 시계열 시퀀스를 구성하는 엔트리들의 전체적인 패턴을 분석하는데 매우 유용하다. 본 논문에서는 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭 방법을 제안한다. 기존의 정규화 변환 지원 서브시퀀스 매칭 방법은 다양한 길이의 질의 시퀀스를 지원하기 위하여 여러 개의 색인을 생성해야 하고, 이에 따라 색인 저장 공간의 오버헤드와 색인 관리의 오버헤드가 발생한다. 본 논문에서는 하나의 색인을 사용하면서도 다양한 길이의 질의 시퀀스에 대한 정규화 변환을 지원하는 효율적인 서브시퀀스 매칭 방법을 제안한다. 이를 위하여, 우선 정규화 변환을 일반화한 포함-정규화 변환(inclusion-normalization transform) 개념을 제시한다. 포함 정규화 변환이란 색인에 저장할 윈도우에 대해서 해당 윈도우를 포함하는 서브시퀀스의 평균과 표준편차로 정규화하는 것으로서, 기본적인 정규화 변환을 윈도우 및 서브시퀀스 개념을 사용하여 확장한 것이다. 다음으로, 포함-정규화 변환을 기존 서브시퀀스 매칭 연구에 적용하기 위한 이론적 근거를 정리로서 제시하고 증명한다. 그리고, 이 방안을 구현하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제시한다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 기존 방법에 비해 최대 $2.5{\sim}2.8$ 배까지 성능을 향상 시킨 것으로 나타났다. 본 논문에서 제안한 정규화 변환 지원 서브시퀀스 매칭은 정규화 변환 이외의 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 따라서, 제안한 방법은 정규화 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시퀀스 매칭에 폭넓게 적용될 수 있는 좋은 연구결과라 사료된다.


    Normalization transform is very useful for finding the overall trend of the time-series data since it enables finding sequences with similar fluctuation patterns. The previous subsequence matching method with normalization transform, however, would incur index overhead both in storage space and in update maintenance since it should build multiple indexes for supporting arbitrary length of query sequences. To solve this problem, we propose a single index approach for the normalization transformed subsequence matching that supports arbitrary length of query sequences. For the single index approach, we first provide the notion of inclusion-normalization transform by generalizing the original definition of normalization transform. The inclusion-normalization transform normalizes a window by using the mean and the standard deviation of a subsequence that includes the window. Next, we formally prove correctness of the proposed method that uses the inclusion-normalization transform for the normalization transformed subsequence matching. We then propose subsequence matching and index building algorithms to implement the proposed method. Experimental results for real stock data show that our method improves performance by up to $2.5{\sim}2.8$ times over the previous method. Our approach has an additional advantage of being generalized to support many sorts of other transforms as well as normalization transform. Therefore, we believe our work will be widely used in many sorts of transform-based subsequence matching methods.


  • 주제어

    데이터 마이닝 .   시계열 데이터베이스 .   서브시퀀스 매칭 .   정규화 변환.  

  • 참고문헌 (17)

    1. Agrawal, R., Faloutsos, C., and Swami, A., 'Efficient Similarity Search in Sequence Databases,' In Proc. the 4th Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, pp.69-84, Oct., 1993 
    2. Agrawal, R., Lin, K.-I., Sawhney, H. S., and Shim, K., 'Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases,' In Proc. the 21st Int'l Conf. on Very Large Data Bases, Zurich, Switzerland, pp.490-501, Sept., 1995 
    3. Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B., 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Atlantic City, New Jersey, pp.322-331, May, 1990 
    4. Chan, K.-P., Fu, A. W. C., and Yu, C. T., 'Haar Wavelets for Efficient Similarity Search of Time-Series: With and Without Time Warping,' IEEE Trans. on Knowledge and Data Engineering, Vol.15, No.3, pp.686-705, Jan./Feb., 2003 
    5. Chu, K. W. and Wong, M. H., 'Fast Time-Series Searching with Scaling and Shifting,' In Proc. the 15th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, pp.237-248, June, 1999 
    6. Faloutsos, C., Ranganathan, M., and Manolopoulos, Y., 'Fast Subsequence Matching in Time-Series Databases,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Minneapolis, Minnesota, pp.419-429, May, 1994 
    7. Kim, S.-W., Park, S, and Chu, W. W., 'Efficient Processing of Similarity Search Under Time Warping in Sequence Databases: An Index-based Approach,' Information Systems, Vol.29, No.5, pp.405-420, July 2004 
    8. Loh, W.-K., Kim, S-W., and Whang, K.-Y., 'Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases,' IEICE Transactions on Information and Systems, Vol.E84-D, No.1, pp.76-86, 2000 
    9. Loh, W.-K., Kim, S.-W., and Whang, K.-Y., 'A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases,' Data Mining and Knowledge Discovery, Vol.9, No.1, pp.5-28, July, 2004 
    10. Moon, Y.-S., Whang, K. Y., and Loh, W.-K., 'Duality-Based Subsequence Matching in Time-Series Databases,' In Proc. the 17th Int'l Conf. on Data Engineering (ICDE), IEEE, Heidelberg, Germany, pp.263-272, April, 2001 
    11. Moon, Y.-S., Whang, K. Y., and Han, W.-S., 'General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Madison, Wisconsin, pp.382-393, June, 2002 
    12. Oppenheim, A. V. and Schafer, R. W., Digital Signal Processing, Prentice-Hall, 1975 
    13. Park, S., Chu, W. W., Yoon, J., and Won, J., 'Similarity Search of Time-Warped Subsequences via a Suffix Tree,' Information Systems, Vol.28, No.7, pp.867-883, Oct., 2003 
    14. Rafiei, D., 'On Similarity-Based Queries for Time Series Data,' In Proc. the 15th Int'l Conf. on Data Engineering(ICDE), IEEE, Sydney, Australia, pp.410-417, Feb., 1999 
    15. Rafiei, D., and Mendelzon, A. O., 'Querying Time Series Data Based on Similarity,' IEEE Trans. on Knowledge and Data Engineering, Vol.12, No.5, pp.675-693, Sept./Oct., 2000 
    16. Wu, H., Salzberg, B., and Zhang, D., 'Online Event-driven Subsequence Matching Over Financial Data Streams,' In Proc. of Int'l Conf. on Management of Data, ACM SIGMOD, Paris, France, pp.23-34, June, 2004 
    17. Yi, B.-K., Jagadish, H. V., and Faloutsos, C., 'Efficient Retrieval of Similar Time Sequences Under Time Warping,' In Proc. the 14th Int'l Conf. on Data Engineering(ICDE), IEEE, Orlando, Florida, pp.201-208, Feb., 1998 

 저자의 다른 논문

  • 문양세 (23)

    1. 2006 "정규화 변환을 지원하는 스트리밍 시계열 매칭 알고리즘" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (6): 600~619    
    2. 2006 "MBR-Safe 변환 : 유사 시퀀스 매칭에서 고차원 MBR의 저차원 변환" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (7): 693~707    
    3. 2006 "단일 색인을 사용한 임의 계수의 이동평균 변환 지원 시계열 서브시퀀스 매칭" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (1): 42~55    
    4. 2006 "통신이력 데이타에 기반한 교우관계 분석" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 33 (8): 730~740    
    5. 2006 "시계열 스트림 데이터 상에서 핸드헬드 디바이스를 위한 효율적인 스트림 시퀀스 매칭 알고리즘" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스 31 (b8): 736~744    
    6. 2007 "부분 집계 근사법의 MBR-안전 성질을 이용한 효율적인 시계열 서브시퀀스 매칭" 정보과학회논문지. Journal of KIISE. 데이타베이스 34 (6): 503~517    
    7. 2008 "시계열 데이타 클러스터링에서 푸리에 진폭 기반의 프라이버시 보호" 정보과학회논문지. Journal of KIISE. 데이타베이스 35 (6): 481~494    
    8. 2010 "시계열 데이터의 프라이버시 보호 클러스터링에서 노이즈 평준화 효과" 정보과학회논문지. Journal of KIISE. 컴퓨팅의 실제 및 레터 16 (3): 356~360    
    9. 2013 "HybridFTW를 사용한 효율적인 k-NN 검색" 정보과학회논문지. Journal of KIISE. 데이타베이스 40 (6): 386~396    
    10. 2014 "시계열 데이터 기반의 부분 노이즈 제거 윤곽선 이미지 매칭" 정보과학회논문지 = Journal of KIISE 41 (11): 943~957    
  • 김진호 (27)

  • 노웅기 (7)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기