GPU-friendly, Parallel, and (Almost-)In-Place Construction of Left-Balanced k-d Trees

Autor:	Wald, Ingo
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Graphics
Druh dokumentu:	Working Paper
Popis:	We present an algorithm that allows for building left-balanced and complete k-d trees over k-dimensional points in a trivially parallel and GPU friendly way. Our algorithm requires exactly one int per data point as temporary storage, and uses O(log N) iterations, each of which performs one parallel sort, and one trivially parallel CUDA per-node update kernel.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2211.00120 Zobrazit plný text záznamu View this record from Arxiv