Parallel Multi-dimensional Range Query Processing with R-Trees on GPU

Jinwoong Kim, Beomseok Nam
School of Electrical and Computer Engineering, Ulsan National Institute of Science and Technology, Ulsan, 689-798, Korea
Ulsan National Institute of Science and Technology, 2013


   title={Parallel Multi-dimensional Range Query Processing with R-Trees on GPU},

   author={Nama, Jinwoong Kima Beomseok},



Download Download (PDF)   View View   Source Source   



The general purpose computing on graphics processing unit (GP-GPU) has emerged as a new cost effective parallel computing paradigm in high performance computing research that enables large amount of data to be processed in parallel. Large scale scientific data intensive applications have been playing an important role in modern high performance computing research. A common access pattern into such scientific data analysis applications is multi-dimensional range query, but not much research has been conducted on multidimensional range query on GP-GPU. Inherently multi-dimensional indexing trees such as R-Trees are not well suited for GPU environment because of its irregular tree traversal. Traversing irregular tree search path makes it hard to maximize the utilization of massively parallel architectures. In this paper, we propose a novel MPTS (Massively Parallel Three-phase Scanning) R-tree traversal algorithm for multi-dimensional range query, that converts recursive access to tree nodes into sequential access. Our extensive experimental study shows that MPTS R-tree traversal algorithm on NVIDIA Tesla M2090 GPU consistently outperforms traditional recursive R-trees search algorithm on Intel Xeon E5506 processors.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: