Fast on-chip quad-trees on GPU

A quad-tree is a desirable data structure for neighbour search in many applications. Due to the irregular nature of trees, however, there is not an efficient implementation of a quad-tree on GPU. In this paper, we propose and set up CUDA-quad-trees on NVIDIA´s GPU+CUDA parallel computing architecture, which takes advantage of the fast on-chip memory of GPU. This data structure for acceleration is used to organize sensor nodes so as to facilitate detection of possible transmitters in simulation of radio propagation in WSNs. Experimental results show that our tree is very efficient and greatly outperforms another CUDA-based tree with one or two order of magnitude speedup in different stages.