GPU Accelerated Range Trees with Applications

Manoj Maramreddy, Kishore Kothapalli
International Institute of Information Technology, Hyderabad, Gachibowli, Hyderabad, India, 500 032
20th Annual International Conference on High Performance Computing (HiPC), 2014


   title={GPU Accelerated Range Trees with Applications},

   author={Maramreddy, Manoj Kumar and Kothapalli, Kishore},

   booktitle={Euro-Par 2014 Parallel Processing},





Download Download (PDF)   View View   Source Source   



Range searching is a primal problem in computational geometry with applications to database systems, mobile computing, geographical information systems, and the like. Defined simply, the problem is to preprocess a given a set of points in a d-dimensional space so that the points that lie inside an orthogonal query rectangle can be efficiently reported. Many practical applications of range trees require one to process a massive amount of points and a massive number of queries. In this context, we propose an efficient parallel implementation of range trees on many-core architectures such as GPUs.We extend our implementation to query processing. While queries can be batched together to exploit inter-query parallelism, we also utilize intra-query parallelism. This inter- and intra-query parallelism greatly reduces the per query latency thereby increasing the throughput. On an input of 1 M points in a 2-dimensional space, our implementation on a single Nvidia GTX 580 GPU for constructing a range tree shows an improvement of 22X over a sequential CPU implementation. We also achieve an average throughput of 10 M queries per second for answering 4 M queries on a range tree containing 1 M points on a Nvidia GTX 580 GPU. We extend our implementation to an application where we seek to report the set of maximal points in a given orthogonal query rectangle.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: