1984년 R-tree가 제안된 이후 R-tree의 질의처리 성능을 높이고자 많은 노력들이 있었다. 하지만, 이러한 노력에도 불구하고 점점 빠르게 커져가는 빅데이타를 처리하기 위한 추가적인 질의처리 성능 개선에 여전히 많은 관심이 집중되고 있다. 본 논문에서는 이러한 문제를 다루고자 CL-tree를 제안한다. 제안 기법은 범위질의 시에 질의영역과 노드의 엔트리들의 포함관계를 고려한다. CL-tree는 범위 질의 시 엔트리들이 질의영역에 포함(contained)되어있다면 중간노드를 방문하지 않고 직접 단말레벨에 접근하기 위해 contain-link라는 포인터를 이용한다. CL-tree의 설계 목표는 트리를 순회할 때 contain-link를 사용하여 불필요한 노드의 방문을 제거함으로써 오는 장점과 GPU의 병렬처리에서 오는 장점을 결합하는 것이다. 다양한 조건에서의 실험을 통해 CL-tree는 GPU에서의 선형검색에 비해 최대 3배, G-tree에 비해 1.3배 가량의 성능이 향상됨을 보인다.
Since the R-tree was proposed in 1984, there have been numerous research efforts on R-tree variants for improving its query performance. Despite all of these efforts, there are still growing interests in further accelerating query performances with the big data that grows faster and bigger in size. To cope with this problem, we propose CL-tree(Contain-Link tree), a novel indexing method that takes into account the relationships between a query range and entries in a node during query processing. Specifically, CL-tree employs a special pointer called contain-link to directly access the leaf level without visiting intermediate nodes when nodes are contained within a given query. The rationale of CL-tree is to combine the benefits from avoiding unnecessary visits during tree traversal using the contain-links and the parallel processing power of GPU. Our extensive experiments show that CL-tree achieves query performance up to 3 times higher than that of a sequential scan in GPU and up to 1.3 times higher than that of a G-tree, respectively.
