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

논문 상세정보

시계열 스트림 데이터 상에서 핸드헬드 디바이스를 위한 효율적인 스트림 시퀀스 매칭 알고리즘

Efficient Stream Sequence Matching Algorithms for Handheld Devices over Time-Series Stream Data

초록

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

Abstract

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.

저자의 다른 논문

참고문헌 (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 

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

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

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

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

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

DOI 인용 스타일