BLAEQ: A Multigrid Index for Spatial Query on Geometry Data

The efficiency of spatial queries is pivotal for the analysis of geometry data in the fields such as computational simulation, point cloud processing and digital engineering. Utilizing the computational capabilities of modern hardware, such as GPUs, offers a promising avenue for accelerating spatial query processing. However, conventional tree-based indexing methods are not optimized for maximal exploitation of GPU resources. To address this problem, we introduce BLAEQ, a multigrid index designed to maximize the potential of GPUs. BLAEQ adopts a multigrid strategy, which represents an index tree with vectors as layers and matrices as connectors. Although BLAEQ shares conceptual similarities with traditional tree-based indexes, its innovative multigrid architecture facilitates effective parallelization on GPUs during the query phase. To optimize GPU utilization, BLAEQ is entirely constructed using BLAS (Basic Linear Algebra Subprograms), leveraging the efficiency of hardware-tuned BLAS libraries like CuBLAS. This design confers BLAEQ with enhanced performance over existing spatial query methods. Our study assesses BLAEQ's performance against state-of-the-art spatial query techniques using a range of both real-world and synthetic datasets. The experimental outcomes demonstrate that BLAEQ outperforms the benchmark approaches in terms of query efficiency on geometry data.