Çѱ¹Á¤º¸Åë½ÅÇÐȸ ³í¹®Áö (Journal of the Korea Institute of Information and Communication Engineering)
ÇѱÛÁ¦¸ñ(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 ´Ù¿î·Îµå
|