III: Medium: Collaborative Research: Spatial Data and Trajectory Data Management on GPUs

虽然智能手机中嵌入的定位和导航设备已经产生了大量的位置和轨迹数据，但下一代消费电子产品可能会产生更大量的位置相关数据，其中空间和轨迹数据管理技术将在理解数据以促进决策方面发挥关键作用。现代图形处理单元（GPU）能够进行通用计算。当前一代的商品GPU具有大量的处理核心，支持更大数量的当前线程，并提供高内存带宽，但价格实惠。GPU的大规模数据并行计算能力使硬件成为数据和计算密集型的空间和轨迹数据管理的理想选择。本项目开发GPU上的空间和轨迹数据的并行索引结构和查询处理算法，以提供高性能，这对于加速现有应用程序和实现新的科学和商业查询至关重要。 该项目通过开发：1）GPU上的新型空间索引技术; 2）GPU上的新型空间连接; 3）GPU上的新型轨迹分割和索引技术以及轨迹相似性查询处理技术;以及4）与开源数据库和GIS系统相结合的端到端原型系统，用于性能评估和真实的世界应用。与现有的大多数驻留在磁盘上并采用串行CPU计算模型的空间和轨迹数据管理系统相比，基于GPU加速的主存系统的性能有望实现几个数量级的加速，并将空间和轨迹查询的性能提升到一个新的水平。 研究成果对交通运输、城市规划、野鸟生态学、传染病流行病学等领域具有重要的应用价值。 合作是与纽约市大学交通研究中心的交通工程师和俄克拉荷马州大学的生态科学家进行的。地球观测和模拟设施。 该项目还对教育产生了重要影响，因为它为学生提供了国家关键需求领域的培训：数据库研究、高性能计算、图形处理器编程、地理信息系统、运输、移动的和生态应用。所开发的算法和原型系统、真实的数据集和性能评估结果可在网站http://www.cs.ou.edu/~database上向公众提供。

Although locating and navigation devices embedded in smartphones have already generated large volumes of location and trajectory data, the next generation of consumer electronics are likely to generate even larger volumes of location-dependent data where spatial and trajectory data management techniques will play critical roles in understanding the data to facilitate decision making. Modern Graphics Processing Units (GPUs) are capable of general computing. Current generation of commodity GPUs have large numbers of processing cores, support even larger numbers of current threads and provide high memory bandwidth, yet are available at affordable prices. The massively data parallel computing power of GPUs makes the hardware ideal for spatial and trajectory data management which is both data and computing intensive.This project develops parallel indexing structures and query processing algorithms for spatial and trajectory data on GPUs to provide high performance which is crucial in speeding up existing applications and enabling new scientific and business inquiries. The project achieves its goals by developing: 1) novel spatial indexing techniques on GPUs; 2) novel spatial joins on GPUs; 3) novel trajectory segmentation and indexing techniques and trajectory similarity query processing techniques on GPUs; and 4) an end-to-end prototype system incorporated with open source database and GIS systems for performance evaluations and real world applications. Compared with existing spatial and trajectory data management systems that are mostly disk-resident and adopt a serial CPU computing model, the performance of GPU accelerated main-memory based systems is expected to achieve several orders of magnitude speedup and brings the performance of spatial and trajectory queries to a new level. The research results are beneficial to many applications, such as transportation, urban planning, wild bird ecology, and epidemiology of infectious diseases. Collaboration is carried out with transportation engineers at the University Transportation Research Center in New York City and ecology scientists at the University of Oklahoma?s Earth Observing and Modelling Facility. The project also makes important impacts on education as it provides training for students in the areas of national critical needs: database research, high performance computing, GPU programming, GIS, transportation, mobile and ecology applications. The developed algorithms and prototype system, real datasets and performance evaluation results are made available to the public at the Website: http://www.cs.ou.edu/~database.