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

논문 상세정보

단일 색인을 사용한 임의 계수의 이동평균 변환 지원 시계열 서브시퀀스 매칭

A Single Index Approach for Time-Series Subsequence Matching that Supports Moving Average Transform of Arbitrary Order

초록

본 논문에서는 단일 색인을 사용하는 임의 계수의 이동평균 변환 지원 서브시퀀스 매칭 방법을 제안한다. 단일 색인을 사용함으로써, 제안한 방법은 색인 저장 공간 및 색인 관리의 오버헤드를 크게 줄일 수 있다. 이동평균 변환은 시계열 데이타 내의 노이즈 영향을 감소시킴으로써, 시계열 데이타 전체의 경향을 파악하는데 매우 유용하다. 그런데, 기존 연구에서는 임의 계수를 지원하기 위해 여러 색인을 생성해야 하고, 이에 따라 색인 저장 공간의 오버헤드와 색인 관리의 오버헤드가 발생하는 문제점이 있다. 본 논문에서는 우선 이동평균 변환의 정의를 확장한 다계수 이동평균 변환(poly-order moving average transform) 개념을 제시한다. 다계수 이동평균 변환이란, 각 윈도우를 하나의 이동평균 계수에 대해서 이동평균 변환하는 것이 아니라, 여러 계수에 대해서 이동평균 변환하여 윈도우의 집합을 구성하는 변환으로서, 이동평균 변환의 정의를 여러 계수로 구성된 집합에 대해서 확장한 것이다. 다음으로, 이러한 다계수 이동평균 변환 개념을 사용한 서브시퀀스 매칭 방법의 이론적 근거인 정확성을 정리로서 제시하고 증명한다. 또한, 다계수 이동평균 변환을 기존 서브시퀀스 매칭 연구인 Faloutsos 둥의 방법 및 DualMatch에 각각 적용하여, 두 가지 이동평균 변환 지원 서브시퀀스 매칭 방법을 제시한다. 실험 결과, 제안한 두 가지 서브시퀀스 매칭 방법은 모든 경우에 있어서 순차 스캔보다 성능을 크게 향상시킨 것으로 나타났다. 실제 주식 데이타에 대한 실험 결과, 제안한 방법은 순차 스캔에 비해서 평균 22.4배${\~}$33.8배까지 성능을 향상시킨 것으로 나타났다. 또한, 각 계수에 대해 모두 색인을 생성하는 경우와 비교할 때, 성능 저하는 매우 적은 반면 필요한 색인 공간은 크게 줄인 것으로 나타났다(일곱 개의 계수를 사용한 경우, 성능 저하는 평균 $9\%{\~}42\%$에 불과한 반면 색인 공간은 약 1/7.0로 크게 줄인다). 이와 같이 성능 측면과 색인 공간 및 관리 측면에서의 우수성에 덧붙여, 제안한 방법은 이동평균 변환 이외의 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있는 장점이 있다 따라서, 제안한 방법은 이동평균 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시퀀스 매칭에 폭넓게 적용되는 우수한 연구결과라 사료된다.

Abstract

We propose a single Index approach for subsequence matching that supports moving average transform of arbitrary order in time-series databases. Using the single index approach, we can reduce both storage space overhead and index maintenance overhead. Moving average transform is known to reduce the effect of noise and has been used in many areas such as econometrics since it is useful in finding overall trends. However, the previous research results have a problem of occurring index overhead both in storage space and in update maintenance since tile methods build several indexes to support arbitrary orders. In this paper, we first propose the concept of poly-order moving average transform, which uses a set of order values rather than one order value, by extending the original definition of moving average transform. That is, the poly-order transform makes a set of transformed windows from each original window since it transforms each window not for just one order value but for a set of order values. We then present theorems to formally prove the correctness of the poly-order transform based subsequence matching methods. Moreover, we propose two different subsequence matching methods supporting moving average transform of arbitrary order by applying the poly-order transform to the previous subsequence matching methods. Experimental results show that, for all the cases, the proposed methods improve performance significantly over the sequential scan. For real stock data, the proposed methods improve average performance by 22.4${\~}$33.8 times over the sequential scan. And, when comparing with the cases of building each index for all moving average orders, the proposed methods reduce the storage space required for indexes significantly by sacrificing only a little performance degradation(when we use 7 orders, the methods reduce the space by up to 1/7.0 while the performance degradation is only $9\%{\~}42\%$ on the average). In addition to the superiority in performance, index space, and index maintenance, the proposed methods have an advantage of being generalized to many sorts of other transforms including moving average transform. Therefore, we believe that our work can be widely and practically used in many sort of transform based subsequence matching methods.

저자의 다른 논문

참고문헌 (20)

  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. 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 
  3. 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 
  4. 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 
  5. 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 
  6. 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 
  7. 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 
  8. 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 
  9. 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 
  10. 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 
  11. 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 
  12. 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 
  13. 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 
  14. 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 
  15. 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 
  16. Chatfield, C., The Analysis of Time Series: An Introduction, 3rd Ed., Chapman and Hall, 1984 
  17. Kendall, M., Time-Series, 2nd Ed., Charles Griffin and Company, 1976 
  18. 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 
  19. Berchtold, S., Bohm, C., and Kriegel, H.-P., 'The Pyramid-Technique: Towards Breaking the Curse of Dimensionality,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Seattle, Washington, pp. 142-153, June 1998 
  20. Oppenheim, A. V. and Schafer, R. W., Digital Signal Processing, Prentice-Hall, 1975 

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

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

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

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

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

DOI 인용 스타일