Back to search

University of South Florida

A GPU-Based Framework for Parallel Spatial Indexing and Query Processing

Abstract

dc:description

Support for efficient spatial data storage and retrieval have become a vital component in almost all spatial database systems. Previous work has shown the importance of using spatial indexing and parallel computing to speed up such tasks. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database applications are busy systems in which a large number of queries arrive simultaneously. In this research, we present a comprehensive framework named G-PICS for parallel processing of a large number of spatial queries on GPUs. G-PICS encapsulates eefficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in Multi-GPU environments to support datasets beyond the size of a single GPU's global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X), and query processing (up to 80X). Moreover, tree update procedure outperforms the tree construction from scratch under different levels of data movement (up to 16X).

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lewis, Zhila Nouri
Contributors dc:contributor
  • Yi-Cheng Tu, Ph.D.
  • Sriram Chellappan, Ph.D.
  • Hao Zheng, Ph.D.
  • Tapas Das, Ph.D.
  • Sagar Pandit, Ph.D.

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/8660

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lewis, Zhila Nouri. A GPU-Based Framework for Parallel Spatial Indexing and Query Processing. Dissertation thesis, University of South Florida, 2019. https://digitalcommons.usf.edu/etd/8660