시계열 데이터베이스에서 효율적인 다단계 k-NN 검색 :Efficient Multi-Step k-NN Search in Time-Series Databases

이상훈

추천

검색

자료유형: 학위논문

저자정보: 이상훈 (강원대학교, 강원대학교 대학원)

지도교수: 문양세

발행연도: 2013

저작권: 강원대학교 논문은 저작권에 의해 보호받습니다.

이용수4

이 논문의 연구 히스토리 (4)

2016

시계열 데이터베이스에서 프라이버시 보호 유사 검색

이상훈 , 김하진 , 문양세 한국정보과학회 학술발표논문집 2016.06 학술대회자료

2013

대용량 시계열 데이터베이스에서 효율적인 다단계 k-NN 검색

이상훈 , 김범수 , 문양세 외 1명 한국정보과학회 학술발표논문집 2013.06 학술대회자료

시계열 데이터베이스에서 효율적인 다단계 k-NN 검색

이상훈 컴퓨터과학과 2013.01 학위논문

2012

시계열 데이터베이스에서 다단계 k-NN 검색의 빠른 근사 접근법

이상훈 , 김범수 , 문양세 외 1명 한국정보과학회 학술발표논문집 2012.11 학술대회자료

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

본 논문에서는 시계열 데이터베이스 대상에서 다단계 k-NN 검색의 성능 향상 문제를 다룬다. 다단계 k-NN 검색은 다차원 인덱스에 k-NN 질의를 수행하고, 그 결과를 검색 범위로 하여 범위 질의를 수행하는 단계적인 시계열 매칭 방법이다. 기존 다단계 k-NN 검색에서는 고차원 시퀀스의 저차원 변환으로 인한 정보 손실로 k-NN 질의 결과 매우 큰 허용치(검색 범위)가 결정된다. 따라서, 범위 질의 결과로 많은 후보가 검색되고, 후처리 과정에서 매우 많은 I/O 및 CPU 오버헤드가 발생하는 문제점이 있다. 본 논문에서는 이와 같은 고찰에 기반하여 범위 질의의 허용치를 줄여 후보 개수를 줄이고 이를 통해 성능을 향상시키는 방법을 제안한다.
먼저, k-NN 질의 결과로 결정된 허용치를 고차원 및 저차원 시퀀스간 거리 비율로 강제 축소하여 범위 질의에 사용하는 허용치 축소 (근사적) 해결책을 제안한다. 이를 위해, 허용치 크기에 따른 허용치 축소 비율을 계산하는 방법을 정형적으로 제안한다. 다음으로, k-NN 질의 계수 k 대신 ck를 사용하여 검색한 후, 수행 결과로 얻은 보다 타이트(tight)한 허용치로 범위 질의를 수행하는 계수 제어 (정확한) 해결책을 제안한다. 본 논문에서는 먼저, 계수 k의 증가 범위를 결정하기 위한 제어상수를 정의하고, 이를 결정하기 위한 c-추정함수 f(k)의 도출 방법을 정형적으로 제시한다.
실험 결과, 제안한 두 가지 해결책은 기존 다단계 k-NN 검색에 비해 후보 개수와 검색 시간 모두를 크게 향상시킨 것으로 나타났다. 제안한 허용치 축소 해결책의 경우, 근사적 해결책에서 발생할 수 있는 착오기각이 발생하지 않거나, 매우 적은 수많이 발생함을 실험을 통해 확인하였다. 이는 제안한 방법이 실제로는 매우 정확하게 시계열 매칭을 수행함을 나타낸다. 또한, 계수 제어 해결책의 경우, 허용치 축소 해결책에서 발생하는 착오기각은 아예 발생시키지 않으면서도 검색 시간은 허용치 축소 해결책에 준하게 향상시킴을 실험을 통해 확인하였다. 이 같은 결과를 볼 때, 제안하는 두 가지 해결책 모두 기존 다단계 k-NN 검색의 기본 구조는 변경하지 않으면서 성능은 향상시킨 매우 우수한 연구라 사료된다.

In this paper, we address a problem of improving the performance of multi-step k-NN search in time-series databases. Due to information loss of lower-dimensional transformations, the existing multi-step k-NN search solution obtains a large tolerance (i.e., a large search range) as a result of k-NN search on a multi-dimensional index. The large tolerance, however, incurs a large number of candidates, which are retrieved by a range query, and those many candidates make severe I/O and CPU overheads in the post processing step. To solve this problem, in this paper we propose two efficient solutions that improve the search performance by intentionally reducing the tolerance of a range query, and accordingly, by reducing the number of candidates.
First, we propose the tolerance reduction-based (approximate) solution that forcibly decreases the tolerance, which is determined by a k-NN query on an index, by the average ratio of high-dimensional and low-dimensional distances. For this, we present a formal method that computes tolerance reduction ratios and determines an appropriate ratio by the given tolerance. Second, we propose the coefficient control-based (exact) solution that uses c?k instead of k in a k-NN query on an index to obtain a tight tolerance and performs a range query using the tight tolerance. For this, we first define the control constant c and the c-estimation function f(k) for determining how much we increase the coefficient k, and we then present a formal method of obtaining f(k) from the statistical analysis on actual data sets.
Experimental results show that the proposed two solutions significantly reduce the number of candidates, and accordingly, improve the search performance in comparison with the existing solution. First, the tolerance reduction-based solution improves the performance by up to 2.6 times compared with the base solution, but it incurs no or a very few number of false dismissals, which are usually occurred in an approximate solution. This means that, even though the tolerance reduction-based solution is an approximate one, it performs the multi-step k-NN search very correctly. Second, the coefficient control-based solution incurs no false dismissal since it is an exact solution, but it shows a comparable performance to the tolerance reduction-based solution. The coefficient control-based solution outperforms the base solution by up to 3.7 times. According to these results, we believe that our approximate and exact solutions are an excellent approach to improve the k-NN search performance without any change of the multi-step k-NN search structure.

#시계열 #시계열 매칭 #다단계 k-NN 검색 #k-NN 검색 #범위 검색

1.서 론 1
2.관련 연구 6
2.1시계열 매칭 6
2.2다단계 k-NN 검색 8
3.연구 동기 12
4.허용치 축소 근사적 해결책 15
4.1개념 15
4.2허용치의 평균 축소 비율 결정 방법 17
4.3성능 평가 22
4.3.1실험 데이터 및 환경 22
4.3.2성능 시험 결과 23
5.계수 제어 정확한 해결책 33
5.1계수 제어 해결책의 개념 및 제어상수 c 정의 33
5.2제어상수 결정 방법 36
5.3성능 평가 40
5.3.1실험 데이터 및 환경 40
5.3.2성능 시험 결과 41
6.결 론 46

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (4)

초록· 키워드

목차

최근 본 자료

댓글(0)