정보과학회 논문지 D : 데이타베이스
Current Result Document : 10 / 11
| 한글제목(Korean Title) |
동적 hilbert Curve 색인을 이용한 효율적인 k-NN 질의 처리 |
| 영문제목(English Title) |
Efficient k-NN Query Processing using Dynamic Hilbert Curve Index |
| 저자(Author) |
서동민
이승우
김 평
정한민
박용훈
유재수
Dongmin Seo
Seungwoo Lee
Pyung Kim
Hanmin Jung
Yonghun Park
Jaesoo Yoo
|
| 원문수록처(Citation) |
VOL 38 NO. 01 PP. 0036 ~ 0041 (2011. 02) |
한글내용
(Korean Abstract) |
이동객체 데이터베이스 분야에서 이동객체의 위치 변경에 대한 대량의 갱신 연산을 빠르게 처리하면서 동시에 대량의 질의를 효과적으로 처리할 수 있는 이동객체 색인에 대한 연구가 진행되고 있다. 최근, R-트리 기반의 이동객체 색인이 가지는 갱신 저하 문제를 해결하기 위해, Hilbert curve를 사용하는 B+-트리 기반의 ST²B-트리가 제안되었다. 하지만 ST²B-트리의 Hilbert curve는 반고정된 해상도(또는 차수, order)를 사용하기 때문에 이동객체가 불균등 분포되면 검색 성능이 현저히 감소하는 문제를 가진다. 그래서 본 논문의 저자들은 Hilbert curve의 해상도를 객체의 분포와 개수에 따라 가변적으로 적용하는 방법을 제안했다. 하지만, ST²B-tree와 제안한 색인의 k-NN 알고리즘은 불필요한 페이지 접근이 발생한다. 따라서 본 논문에서는 k-NN 질의 처리 성능을 향상시킬 수 있는 향상된 k-NN 알고리즘을 제안한다. 또한, 실험을 통해서 제안하는 기법이 ST²B-tree에 비해 향상되었음을 보인다.
|
영문내용
(English Abstract) |
In the field of a moving object database, studies on moving object indexes have been progressed. Moving object indexes handle frequent updates of object's locations and many queries of users efficiently. To solve a lowering of the update performance of moving object indexes based on R-tree, ST2B-tree that uses the Hilbert curve and is based on B -tree is proposed recently. However, if moving objects are skewed, the update performance of ST2B-tree has a rapid decline because the Hilbert curve of ST2B-tree has a semi-fixed order. Therefore, we proposed an advanced Hilbert curve that adjusts automatically the order of Hilbert curve according to the data distribution and the number of moving objects. However, k-NN algorithms of ST2B-tree and our index have a lot of unnecessary page accesses. In this paper, we propose an advanced k-NN algorithm to improve the k-NN performance. We show that our algorithm is better than ST2B-tree by experiments.
|
| 키워드(Keyword) |
k-NN
Hilbert Curve
색인
이동객체
위치기반 서비스
Index
Moving Object
Location-based Service
|
| 파일첨부 |
PDF 다운로드
|
