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加速的主存系统的性能有望实现数个数量级的提升，并将空间和轨迹查询的性能提升到一个新的水平。研究成果在交通运输、城市规划、野鸟生态学、传染病流行病学等方面具有广泛的应用价值。纽约市大学交通研究中心的交通工程师和俄克拉何马大学的生态科学家进行了合作。s地球观测及模拟设施。该项目还对教育产生了重要影响，因为它为学生提供了国家关键需求领域的培训：数据库研究、高性能计算、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.