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: www.cs.ou.edu/~database.
