GPU에서 Contain-Link를 이용한 R-tree 구현 = Implementation of the R-tree using Contain-Links on GPU

국문 초록 (Abstract)

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배 가량의 성능이 향상됨을 보인다.

다국어 초록 (Multilingual Abstract)

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.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. CL-tree 의 구조 및 검색과정
• 4. 실험
• 5. 결론
• References

참고문헌 (Reference)

1 S. Berchtold, "The X-tree: An Index Structure for High-Dimensional Data" 28-39, 1996

2 T. Sellis, "The R+-tree: A dynamic index for multi-dimensional objects" 507-518, 1987

3 N. Beckmann, "The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles" 322-331, 1990

4 H. Bay, "Speeded-up robust features (SURF)" 110 (110): 346-359, 2008

5 A. Guttman, "R-trees: a dynamic index structure for spatial searching" 47-57, 1984

6 I. Kamel, "Parallel R-trees" 195-204, 1992

7 L. Luo, "Parallel Implementation of R-trees on the GPU" 353-358, 2012

8 R. Bayer, "Organization and Maintenance of Large Ordered Indices" 1 (1): 173-189, 1972

9 "OpenCV library"

10 B. Schnitzer, "Master-Client R-trees: A New Parallel R-tree Architecture" 68-77, 1999

11 김민철, "GPU에서 효율적인 병렬처리를 위한 R-tree 질의 처리 기법" 한국정보과학회 18 (18): 409-413, 2012

12 N. Koudas, "Declustering Spatial Databases on a MultiComputer Architecture" 592-614, 1996