GPGPU를 이용한 Hilbert R-tree 벌크로딩 고속화 기법

양시동; 최원익; Sidong Yang; Wonik Choi

연구문헌

국내 논문지

홈 > 연구문헌 > 국내 논문지 > 한국정보과학회 논문지 > 정보과학회논문지 (Journal of KIISE)

정보과학회논문지 (Journal of KIISE)

Current Result Document : 93 / 397 이전건 다음건

한글제목(Korean Title)	GPGPU를 이용한 Hilbert R-tree 벌크로딩 고속화 기법
영문제목(English Title)	Fast Hilbert R-tree Bulk-loading Scheme using GPGPU
저자(Author)	양시동 최원익 Sidong Yang Wonik Choi
원문수록처(Citation)	VOL 41 NO. 10 PP. 0792 ~ 0798 (2014. 10)
한글내용 (Korean Abstract)	R-tree는 공간 데이터베이스 분야에서 가장 널리 쓰이는 색인 구조이며 다양한 변형된 기법들이 제안되었다. 이 기법들 중 Hilbert R-tree는 공간 채움 곡선인 Hilbert 곡선을 이용해서 대용량의 데이터를 고비용의 분할 과정 없이 R-tree를 구성하는 기법이다. 하지만 기존의 CPU기반의 Hilbert R-tree는 대용량의 데이터를 처리할 때는 순차적인 접근으로 발생되는 고비용의 전처리 비용과 느린 구축시간으로 실제 응용에 적용되기에는 한계가 있다. 본 논문에서는 이러한 문제를 해결하기 위해 GPU를 이용해서 데이터의 Hilbert 매핑을 병렬화 하고 이를 통해서 최종적으로 GPU의 메모리에 Hilbert R-tree의 벌크로딩을 고속화하는 기법을 제안한다. GPU기반의 Hilbert R-tree는 inversed-cell 기법과 트리구조 패킹의 병렬화 기법을 통해서 벌크로딩의 성능을 향상시켰다. 실험 결과에서는 기존의 CPU 기반의 벌크로딩에 비해 최대 45배의 성능향상을 보여주었다.
영문내용 (English Abstract)	In spatial databases, R-tree is one of the most widely used indexing structures and many variants have been proposed for its performance improvement. Among these variants, Hilbert R-tree is a representative method using Hilbert curve to process large amounts of data without high cost split techniques to construct the R-tree. This Hilbert R-tree, however, is hardly applicable to large-scale applications in practice mainly due to high pre-processing costs and slow bulk-load time. To overcome the limitations of Hilbert R-tree, we propose a novel approach for parallelizing Hilbert mapping and thus accelerating bulk-loading of Hilbert R-tree on GPU memory. Hilbert R-tree based on GPU improves bulk-loading performance by applying the inversed-cell method and exploiting parallelism for packing the R-tree structure. Our experimental results show that the proposed scheme is up to 45 times faster compared to the traditional CPU-based bulk-loading schemes.
키워드(Keyword)	공간 데이터베이스 Hilbert R-tree GPGPU spatial database hilbert R-tree GPGPU
파일첨부	PDF 다운로드