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

논문 상세정보

시계열 스트림 데이터 상에서 핸드헬드 디바이스를 위한 효율적인 스트림 시퀀스 매칭 알고리즘
Efficient Stream Sequence Matching Algorithms for Handheld Devices over Time-Series Stream Data

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

    핸드헬드 디바이스의 경우, 반복 작업에 대한 CPU 연산 최소화가 성능에 중요한 요소이다. 본 논문에서는 주식 데이터, 네트워크 트래픽, 센서 데이터 등의 시계열 스트림 데이터 상에서 유사 시퀀스를 효율적으로 찾아내는 핸드헬드 디바이스용 알고리즘을 제시한다. 이를 위하여, 우선 시계열 스트림 데이터 상에서 유사 시퀀스를 찾아내는 문제를 스트림 시퀀스 매칭(stream sequence matching)으로 정형적으로 정의한다. 다음으로, 기존의 서브시퀀스 매칭에서 사용했던 윈도우 구성법을 적용하여, 스트림 시퀀스 매칭을 효율적으로 처리하는 윈도우 기반 접근법을 제안한다. 그리고 이러한 윈도우 기반 접근법을 가능하게 하는 윈도우 MBR(window MBR) 개념을 제시하고, 이 개념을 사용하면 스트림 시퀀스 매칭을 정확하게 수행할 수 있음을 증명한다. 또한, 윈도우 기반 접근법에 기반한 두 가지 스트림 시퀀스 매칭 알고리즘을 제안한다. 마지막으로, 분석과 실험을 통해 제안한 알고리즘이 단순 접근법에 비해 CPU 연산을 크게 줄이고 성능을 향상시킴을 보인다. 이 같은 결과를 볼 때, 제안한 방법은 CPU 연산 능력이 부족한 핸드헬드 디바이스의 내장형 알고리즘으로 매우 적합하다고 사료된다.


    For the handhold devices, minimizing repetitive CPU operations such as multiplications is a major factor for their performances. In this paper, we propose efficient algorithms for finding similar sequences from streaming time-series data such as stock prices, network traffic data, and sensor network data. First, we formally define the problem of similar subsequence matching from streaming time-series data, which is called the stream sequence matching in this paper. Second, based on the window construction mechanism adopted by the previous subsequence matching algorithms, we present an efficient window-based approach that minimizes CPU operations required for stream sequence matching. Third, we propose a notion of window MBR and present two stream sequence matching algorithms based on the notion. Fourth, we formally prove correctness of the proposed algorithms. Finally, through a series of analyses and experiments, we show that our algorithms significantly outperform the naive algorithm. We believe that our window-based algorithms are excellent choices for embedded stream sequence matching in handhold devices.


  • 주제어

    Stream data .   Time-series data .   Stream sequence matching .   Handhold devices.  

  • 참고문헌 (12)

    1. Agrawal, R., Faloutsos, C., and Swami, A., 'Efficient Similarity Search in Sequence Databases,' In Proc. Int'l Conf on FODO, pp. 69-84, Oct. 1993 
    2. Babcock, B., et al., 'Models and Issues in Data Stream Systems,' In Proc. of ACM PODS, pp. 1-16, June 2002 
    3. Fluke Electronics, http://www.fluke.com/ 
    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. of ACM SIGMOD, pp. 382-393, June 2002 
    5. Gao, L. and Wang, X. S., 'Continually Evaluating Similarity-based Pattern Queries on a Stream Time Series,' In Proc. of ACM SIGMOD, pp. 370-381, June 2002 
    6. Faloutsos, C, Ranganathan, M, and Manolopoulos, Y., 'Fast Subsequence Matching in Time-Series Databases,' In Proc. of ACM SIGMOD, pp. 419-429, May 1994 
    7. Stevens, W. R., Advanced Programming in the UNIX Environment, Addison-Wesley, 1992 
    8. 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 TKDE, VoL.15, No.3, pp.686-705, Jan./Feb. 2003 
    9. Medvidovic, N., et al., 'Software Architectural Support for Handheld Computing,' IEEE Computer, Vol. 36, No.9, pp.66-73, Sept., 2003 
    10. Moon, Y.-S., Whang, K.-Y., and Loh, W.-K., 'Efficient Time-Series Subsequence Matching using Duality in Constructing Windows,' Information Systems, Vol.26, No.4, pp.279-293, June, 2001 
    11. Wu, H., Salzberg, B., and Zhang, D., 'Online Event-driven Subsequence Matching Over Financial Data Streams,' In Proc. of ACM SIGMOD, pp. 23-34, June 2004 
    12. Gao, L., Yao, Z., and Wang, X. S., 'Evaluating Continuous Nearest Neighbor Queries for Streaming Time Series via Pre-fetching,' In Proc. of ACM CIKM, pp.485-492, 2002 

 저자의 다른 논문

  • 문양세 (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 "시계열 데이터베이스에서 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭" 정보처리학회논문지. The KIPS transactions. Part D. Part D d13 (4): 513~524    
    5. 2006 "통신이력 데이타에 기반한 교우관계 분석" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 33 (8): 730~740    
    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    
  • 노웅기 (7)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

이 논문과 함께 출판된 논문 + 더보기