Scholarlink

With advancements in location sensing, spatial data is increasing in volume and value. A fundamental problem in spatial databases, the point-in-polygon (PIP) query, returns points within a (set of) given polygon(s) and has broad applications in location-based services. Using the GPU rendering pipeline to replace traditional PIP tests is a promising approach. However, due to the limited color channel space per pixel, this paradigm faces challenges in effectively distinguishing the IDs of points and polygons. We address these challenges by categorizing PIP queries into two types. Based on the characteristics of each type, we study the impact of different rendering methods when converting PIP tests into object-rendering operations. This enables us to judiciously choose the storage modes for point and polygon IDs, tailored for each type. Extensive experiments show that our method effectively leverages the GPU’s native rendering capabilities, outperforming existing solutions by one to three orders of magnitude.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

RasterPIP: Answering Point-in-Polygon Query with GPU-Native Transformation and Rasterization

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Ziang Liu,
  • Hui Li,
  • Yingfan Liu,
  • Hua Tong,
  • Zhenning Shi,
  • Hui Zhang,
  • Jiangtao Cui

摘要

With advancements in location sensing, spatial data is increasing in volume and value. A fundamental problem in spatial databases, the point-in-polygon (PIP) query, returns points within a (set of) given polygon(s) and has broad applications in location-based services. Using the GPU rendering pipeline to replace traditional PIP tests is a promising approach. However, due to the limited color channel space per pixel, this paradigm faces challenges in effectively distinguishing the IDs of points and polygons. We address these challenges by categorizing PIP queries into two types. Based on the characteristics of each type, we study the impact of different rendering methods when converting PIP tests into object-rendering operations. This enables us to judiciously choose the storage modes for point and polygon IDs, tailored for each type. Extensive experiments show that our method effectively leverages the GPU’s native rendering capabilities, outperforming existing solutions by one to three orders of magnitude.