  The availability of low cost sensors has led to an unprecedented growth in
the volume of spatial data. However, 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. Graphics
Processing Units~(GPUs) are increasingly being used to speedup spatial queries.
However, existing GPU-based 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 by formulating standard spatial queries as algebraic
expressions. We also present a proof-of-concept prototype that supports a
subset of the operators and show that it is at least two orders of magnitude
faster than a CPU-based implementation. This performance gain is obtained both
using a discrete Nvidia mobile GPU and the less powerful integrated GPUs common
in commodity laptops.
