TY - GEN
T1 - A GPU-friendly Geometric Data Model and Algebra for Spatial Queries
AU - Doraiswamy, Harish
AU - Freire, Juliana
N1 - Funding Information:
Acknowledgements. This work was partially supported by the DARPA D3M program, the NYU Moore Sloan Data Science Environment, and NSF award CCF-1533564.
PY - 2020/6/14
Y1 - 2020/6/14
N2 - The availability of low cost sensors has led to an unprecedented growth in the volume of spatial data. Unfortunately, the time required to evaluate even simple spatial queries over large data sets greatly hampers our ability to interactively explore these data sets and extract actionable insights. While Graphics Processing Units∼(GPUs) are increasingly being used to speed up spatial queries, existing solutions have two important drawbacks: they are often tightly coupled to the specific query types they target, making it hard to adapt them for other queries; and since their design is based on CPU-based approaches, it can be difficult to effectively utilize all the benefits provided by the GPU. As a first step towards making GPU spatial query processing mainstream, we propose a new model that represents spatial data as geometric objects and define an algebra consisting of GPU-friendly composable operators that operate over these objects. We demonstrate the expressiveness of the proposed algebra and present a proof-of-concept prototype that supports a subset of the operators, which shows that it is orders of magnitude faster than a CPU-based implementation and outperforms custom GPU-based approaches.
AB - The availability of low cost sensors has led to an unprecedented growth in the volume of spatial data. Unfortunately, the time required to evaluate even simple spatial queries over large data sets greatly hampers our ability to interactively explore these data sets and extract actionable insights. While Graphics Processing Units∼(GPUs) are increasingly being used to speed up spatial queries, existing solutions have two important drawbacks: they are often tightly coupled to the specific query types they target, making it hard to adapt them for other queries; and since their design is based on CPU-based approaches, it can be difficult to effectively utilize all the benefits provided by the GPU. As a first step towards making GPU spatial query processing mainstream, we propose a new model that represents spatial data as geometric objects and define an algebra consisting of GPU-friendly composable operators that operate over these objects. We demonstrate the expressiveness of the proposed algebra and present a proof-of-concept prototype that supports a subset of the operators, which shows that it is orders of magnitude faster than a CPU-based implementation and outperforms custom GPU-based approaches.
KW - GPU processing
KW - spatial query model
UR - http://www.scopus.com/inward/record.url?scp=85086223480&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086223480&partnerID=8YFLogxK
U2 - 10.1145/3318464.3389774
DO - 10.1145/3318464.3389774
M3 - Conference contribution
AN - SCOPUS:85086223480
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 1875
EP - 1885
BT - SIGMOD 2020 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
PB - Association for Computing Machinery
T2 - 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD 2020
Y2 - 14 June 2020 through 19 June 2020
ER -