A Versatile and Efficient GPU Data Structure for Spatial Indexing

Jens Schneider; Peter Rautek

doi:10.1109/TVCG.2016.2599043

A Versatile and Efficient GPU Data Structure for Spatial Indexing

Jens Schneider, Peter Rautek

King Abdullah University of Science and Technology

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

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.

Original language	English
Article number	7539577
Pages (from-to)	911-920
Number of pages	10
Journal	IEEE Transactions on Visualization and Computer Graphics
Volume	23
Issue number	1
DOIs	https://doi.org/10.1109/TVCG.2016.2599043
Publication status	Published - Jan 2017
Externally published	Yes

Keywords

Binary Index Trees
GPU-based Data Structures
Sparse Data

Access to Document

10.1109/TVCG.2016.2599043

Cite this

@article{22804fbb971a4ca5baf5e4014642d18e,

title = "A Versatile and Efficient GPU Data Structure for Spatial Indexing",

abstract = "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.",

keywords = "Binary Index Trees, GPU-based Data Structures, Sparse Data",

author = "Jens Schneider and Peter Rautek",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.",

year = "2017",

month = jan,

doi = "10.1109/TVCG.2016.2599043",

language = "English",

volume = "23",

pages = "911--920",

journal = "IEEE Transactions on Visualization and Computer Graphics",

issn = "1077-2626",

publisher = "IEEE Computer Society",

number = "1",

}

TY - JOUR

T1 - A Versatile and Efficient GPU Data Structure for Spatial Indexing

AU - Schneider, Jens

AU - Rautek, Peter

PY - 2017/1

Y1 - 2017/1

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.

KW - Binary Index Trees

KW - GPU-based Data Structures

KW - Sparse Data

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

C2 - 27875204

AN - SCOPUS:84999040425

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

M1 - 7539577

ER -

A Versatile and Efficient GPU Data Structure for Spatial Indexing

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this