http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
동적 Hilbert Curve 색인을 이용한 효율적인 k- NN 질의 처리
서동민(Dongmin Seo),이승우(Seungwoo Lee),김평(Pyung Kim),정한민(Hanmin Jung),박용훈(Yonghun Park),유재수(Jaesoo Yoo) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.1
이동객체 데이터베이스 분야에서 이동객체의 위치 변경에 대한 대량의 갱신 연산을 빠르게 처리하면서 동시에 대량의 질의를 효과적으로 처리할 수 있는 이동객체 색인에 대한 연구가 진행되고 있다. 최근, 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에 비해 향상되었음을 보인다. 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²B-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²B-tree has a rapid decline because the Hilbert curve of ST²B-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²B-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²B-tree by experiments.