论文标题
适用于GPU的几何数据模型和空间查询的代数：扩展版本
A GPU-friendly Geometric Data Model and Algebra for Spatial Queries: Extended Version
论文作者
论文摘要
低成本传感器的可用性导致空间数据量的前所未有的增长。但是，在大型数据集上评估简单的空间查询所需的时间极大地阻碍了我们交互式探索这些数据集并提取可行的见解的能力。图形处理单元〜（GPU）越来越多地用于加速空间查询。但是，现有的基于GPU的解决方案有两个重要的缺点：它们通常与它们针对的特定查询类型紧密耦合，从而使它们很难适应其他查询；而且由于它们的设计基于基于CPU的方法，因此很难有效利用GPU提供的所有好处。作为制作GPU空间查询处理主流的第一步，我们提出了一个新模型，该模型代表空间数据作为几何对象，并定义一个由对GPU友好型综合运算符组成的代数，该代数可在这些对象上运行。我们通过将标准空间查询作为代数表达式来证明所提出的代数的表现力。我们还提出了概念验证原型，该原型支持运营商的一部分，并表明它比基于CPU的实现更快两个数量级。使用离散的NVIDIA移动GPU和商品笔记本电脑中常见的不太强大的集成GPU获得了这种性能增长。
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.
