이 논문에서는 고차원 색인 구조인 CIR-트리를 위한 효율적인 벌크로딩 알고리즘을 설계하고 구현한다. 벌크로딩 기법은 대량의 고차원 데이타가 색인 구성 시 함께 주어지는 경우 색인의 구성을 빠르게 하고 구축한 색인의 검색 성능을 향상시킨다. CIR-트리는 반드시 필요한 차원만 이용해서 비단말 노드의 엔트리를 구성하기 때문에 엔트리 크기가 일정하지 않다. 이 특성은 비단말 노드의 분기율을 높이고 탐색 성능을 향상시키는 효과가 있다. 기존에 다차원 및 고차원 색인구조를 위한 벌크로딩 기법이 제안되었지만 이러한 CIR-트리의 특징을 제대로 살릴 수 있는 방법은 없다. 이 논문에서는 기존의 벌크로딩 알고리즘을 개선하면서 CIR-트리의 특징을 효과적으로 색인 구성에 반영할 수 있는 알고리즘을 제안한다. 또한 이를 BADA-III의 하부 저장 시스템인 MiDAS-III에서 구현하고 다양한 실험을 통해 그 성능을 입증한다.
In this paper, we design and implement an efficient bulk-loading algorithm for CIR-Tree. Bulk-loading techniques increase node utilization, improve query performance and reduce index construction time. The CIR-tree has variable size of internal node entries since it only maintains minimal dimensions to decriminate child nodes. This property increases fan-out of internal nodes and improves search performance. Even though several bulk-loading algorithms for multi/high-dimensional index structures have been proposed, we cannot apple them to CIR-tree because of the variable size of internal node entries. In this paper, we propose an efficient bulk- loading algorithm for CIR-tree that improves the existing bulk-loading algorithm and accomodates the property of CIR-tree. We also implement it on a storage system MiDAS-III and show superiority of our algorithm through various experiments.
