IEICE TRANSACTIONS on Information
Accelerating Range Query Processing on R-Tree Using Graphics Processing Units
Summary :
Recently, various research efforts have been conducted to develop strategies for accelerating multi-dimensional query processing using the graphics processing units (GPUs). However, well-known multi-dimensional access methods such as the R-tree, B-tree, and their variants are hardly applicable to GPUs in practice, mainly due to the characteristics of a hierarchical index structure. More specifically, the hierarchical structure not only causes frequent transfers of small volumes of data but also provides limited opportunity to exploit the advanced data parallelism of GPUs. To address these problems, we propose an approach that uses GPUs as a buffer. The main idea is that object entries in recently visited leaf nodes are buffered in the global memory of GPUs and processed by massive parallel threads of the GPUs. Through extensive performance studies, we observed that the proposed approach achieved query performance up to five times higher than that of the original R-tree.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.12 pp.2776-2785
- Publication Date
- 2013/12/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.2776
- Type of Manuscript
- PAPER
- Category
- Data Engineering, Web Information Systems
Authors
Boseon YU
Inha University
Hyunduk KIM
Inha University
Wonik CHOI
Inha University
Dongseop KWON
Myongji University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Boseon YU, Hyunduk KIM, Wonik CHOI, Dongseop KWON, "Accelerating Range Query Processing on R-Tree Using Graphics Processing Units" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 12, pp. 2776-2785, December 2013, doi: 10.1587/transinf.E96.D.2776.
Abstract: Recently, various research efforts have been conducted to develop strategies for accelerating multi-dimensional query processing using the graphics processing units (GPUs). However, well-known multi-dimensional access methods such as the R-tree, B-tree, and their variants are hardly applicable to GPUs in practice, mainly due to the characteristics of a hierarchical index structure. More specifically, the hierarchical structure not only causes frequent transfers of small volumes of data but also provides limited opportunity to exploit the advanced data parallelism of GPUs. To address these problems, we propose an approach that uses GPUs as a buffer. The main idea is that object entries in recently visited leaf nodes are buffered in the global memory of GPUs and processed by massive parallel threads of the GPUs. Through extensive performance studies, we observed that the proposed approach achieved query performance up to five times higher than that of the original R-tree.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.2776/_p
Copy
@ARTICLE{e96-d_12_2776,
author={Boseon YU, Hyunduk KIM, Wonik CHOI, Dongseop KWON, },
journal={IEICE TRANSACTIONS on Information},
title={Accelerating Range Query Processing on R-Tree Using Graphics Processing Units},
year={2013},
volume={E96-D},
number={12},
pages={2776-2785},
abstract={Recently, various research efforts have been conducted to develop strategies for accelerating multi-dimensional query processing using the graphics processing units (GPUs). However, well-known multi-dimensional access methods such as the R-tree, B-tree, and their variants are hardly applicable to GPUs in practice, mainly due to the characteristics of a hierarchical index structure. More specifically, the hierarchical structure not only causes frequent transfers of small volumes of data but also provides limited opportunity to exploit the advanced data parallelism of GPUs. To address these problems, we propose an approach that uses GPUs as a buffer. The main idea is that object entries in recently visited leaf nodes are buffered in the global memory of GPUs and processed by massive parallel threads of the GPUs. Through extensive performance studies, we observed that the proposed approach achieved query performance up to five times higher than that of the original R-tree.},
keywords={},
doi={10.1587/transinf.E96.D.2776},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Accelerating Range Query Processing on R-Tree Using Graphics Processing Units
T2 - IEICE TRANSACTIONS on Information
SP - 2776
EP - 2785
AU - Boseon YU
AU - Hyunduk KIM
AU - Wonik CHOI
AU - Dongseop KWON
PY - 2013
DO - 10.1587/transinf.E96.D.2776
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2013
AB - Recently, various research efforts have been conducted to develop strategies for accelerating multi-dimensional query processing using the graphics processing units (GPUs). However, well-known multi-dimensional access methods such as the R-tree, B-tree, and their variants are hardly applicable to GPUs in practice, mainly due to the characteristics of a hierarchical index structure. More specifically, the hierarchical structure not only causes frequent transfers of small volumes of data but also provides limited opportunity to exploit the advanced data parallelism of GPUs. To address these problems, we propose an approach that uses GPUs as a buffer. The main idea is that object entries in recently visited leaf nodes are buffered in the global memory of GPUs and processed by massive parallel threads of the GPUs. Through extensive performance studies, we observed that the proposed approach achieved query performance up to five times higher than that of the original R-tree.
ER -
English
