Parallelizing the Construction of a k-Dimensional Tree
Hiroki Yamasaki, Atsushi Nunome, Hiroaki Hirata · 2018
k-dimensional (k-d) trees are one of the most important data structures in the fields of data engineering and so-called Big Data. In this paper we propose a scheme parallelizing the construction of a k-d tree. Since efficient presorting is required for constructing a balanced k-d tree, we also developed a parallelized heapsort algorithm. The proposed scheme is 3.59 times faster than sequential construction of a k-d tree.