TY - JOUR
T1 - A Versatile and Efficient GPU Data Structure for Spatial Indexing
AU - Schneider, Jens
AU - Rautek, Peter
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The authors’ work is funded by the Visual Computing Center (VCC) at King Abdullah University of Science and Technology (KAUST). Volume data sets were obtained from VolVis.org, TU Wien, and Digi-Morph. The vessel data set was provided by John Keyser, TAMU.
PY - 2016/8/10
Y1 - 2016/8/10
N2 - In this paper we present a novel GPU-based data structure for spatial indexing. Based on Fenwick trees—a special type of binary indexed trees—our data structure allows construction in linear time. Updates and prefixes can be computed in logarithmic time, whereas point queries require only constant time on average. Unlike competing data structures such as summed-area tables and spatial hashing, our data structure requires a constant amount of bits for each data element, and it offers unconstrained point queries. This property makes our data structure ideally suited for applications requiring unconstrained indexing of large data, such as block-storage of large and block-sparse volumes. Finally, we provide asymptotic bounds on both run-time and memory requirements, and we show applications for which our new data structure is useful.
AB - In this paper we present a novel GPU-based data structure for spatial indexing. Based on Fenwick trees—a special type of binary indexed trees—our data structure allows construction in linear time. Updates and prefixes can be computed in logarithmic time, whereas point queries require only constant time on average. Unlike competing data structures such as summed-area tables and spatial hashing, our data structure requires a constant amount of bits for each data element, and it offers unconstrained point queries. This property makes our data structure ideally suited for applications requiring unconstrained indexing of large data, such as block-storage of large and block-sparse volumes. Finally, we provide asymptotic bounds on both run-time and memory requirements, and we show applications for which our new data structure is useful.
UR - http://hdl.handle.net/10754/620933
UR - http://ieeexplore.ieee.org/document/7539577/
UR - http://www.scopus.com/inward/record.url?scp=84999040425&partnerID=8YFLogxK
U2 - 10.1109/TVCG.2016.2599043
DO - 10.1109/TVCG.2016.2599043
M3 - Article
SN - 1077-2626
VL - 23
SP - 911
EP - 920
JO - IEEE Transactions on Visualization and Computer Graphics
JF - IEEE Transactions on Visualization and Computer Graphics
IS - 1
ER -