검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases 인덱스 보간: 시계열 데이터베이스에서 임의 순서의 이동 평균 변환을 지원하는 하위 시퀀스 매칭 알고리즘

Woong-Kee LOH, Sang-Wook KIM, Kyu-Young WHANG

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문에서는 시계열 데이터베이스에서 임의 순서의 이동 평균 변환을 지원하는 하위 시퀀스 매칭 알고리즘을 제안합니다. 이동 평균 변환은 잡음의 영향을 줄여주며 전반적인 추세를 찾는 데 유용하므로 계량경제학 등 다양한 분야에서 사용되어 왔습니다. 제안된 알고리즘은 Faloutsos et al.이 제안한 기존 하위 시퀀스 매칭 알고리즘을 확장합니다. (줄여서 SUB94). 확장 없이 알고리즘을 적용하면 각 이동 평균 주문에 대한 인덱스를 생성해야 하며 심각한 저장 공간 및 CPU 시간 오버헤드가 발생합니다. 본 논문에서는 인덱스 보간(index interpolation) 개념을 사용하여 문제를 해결합니다. 인덱스 보간 선택된 몇 가지 사례에 대해 생성된 하나 이상의 색인을 사용하여 일부 기준을 만족하는 모든 사례를 검색하는 검색 방법으로 정의됩니다. 인덱스 보간에 기반한 제안 알고리즘은 미리 선택된 이동평균 차수에 대해 하나의 인덱스만을 사용할 수 있다. k 임의의 순서에 대해 하위 시퀀스 일치를 수행합니다. m ( k). 우리는 제안한 알고리즘이 거짓 해고를 유발하지 않음을 증명합니다. 제안된 알고리즘은 검색 성능을 향상시키기 위해 하나 이상의 인덱스를 사용할 수도 있습니다. 이 알고리즘은 선택성이 작을수록 더 잘 작동합니다. 선택성이 10 미만인 경우-2, Full-indexed 경우(SUB94와 동일)에 비해 검색 성능 저하가 33.0개 인덱스 사용 시 17.2%, XNUMX개 인덱스 사용 시 XNUMX%를 넘지 않습니다. 일반적인 데이터베이스 응용에서는 선택성이 작은 질의가 훨씬 더 빈번하기 때문에 제안하는 알고리즘은 실제 상황에 적합하다.

발행
IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.76-86
발행일
2001/01/01
공개일
온라인 ISSN
DOI
원고의 종류
PAPER
범주
데이터베이스

작성자

키워드