동적 Hilbert Curve 색인을 이용한 효율적인 k-NN 질의 처리 (Efficient k-NN Query Processing using Dynamic Hilbert Curve Index)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 38권 / 1호 / 36 ~ 41페이지
· 저자명 : 서동민, 이승우, 김평, 정한민, 박용훈, 유재수

초록

이동객체 데이터베이스 분야에서 이동객체의 위치 변경에 대한 대량의 갱신 연산을 빠르게 처리하면서 동시에 대량의 질의를 효과적으로 처리할 수 있는 이동객체 색인에 대한 연구가 진행되고 있다. 최근, R-트리 기반의 이동객체 색인이 가지는 갱신 저하 문제를 해결하기 위해, Hilbert curve를 사용하는 B+-트리 기반의 ST^2B-트리가 제안되었다. 하지만, ST^2B-트리의 Hilbert curve는 반고정된 해상도(또는 차수, order)를 사용하기 때문에 이동객체가 불균등 분포되면 검색 성능이 현저히 감소하는 문제를 가진다. 그래서 본 논문의 저자들은 Hilbert curve의 해상도를 객체의 분포와 개수에 따라 가변적으로 적용하는 방법을 제안했다. 하지만, ST^2B-tree와 제안한 색인의 k-NN 알고리즘은 불필요한 페이지 접근이 발생한다. 따라서 본 논문에서는 k-NN 질의 처리 성능을 향상시킬 수 있는 향상된 k-NN 알고리즘을 제안한다. 또한, 실험을 통해서 제안하는 기법이 ST^2B-tree에 비해 향상되었음을 보인다.

영어초록

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, ST^2B-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 ST^2B-tree has a rapid decline because the Hilbert curve of ST^2B-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 ST^2B-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 ST^2B-tree by experiments.

참고자료

· 없음