HPG-Tree: An Enhanced <i>B⁺ </i>-Tree for Spatial Indexing

In modern applications such as geographic information systems, game development, and image processing, the demand for efficient two-dimensional spatial indexing is rising exponentially. Traditional approaches like <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i>-tree can suffer from excessive overlap and fragmentation, while standard <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-trees are limited to one-dimensional data. Motivated by these gaps, we propose the hyperbolic paraboloid grid (HPG) tree, an enhanced <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-tree structure specifically tailored for two-dimensional datasets. First, we employ a grid-based strategy that maps two-dimensional points into one-dimensional values without resorting to hashing. By combining grid partitioning with the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-tree’s efficient, self-balancing properties, the HPG-tree simultaneously addresses overlap, storage utilization, and query performance. Unlike purely one-dimensional indexes, this method preserves spatial locality and avoids excessive rebalancing. Further, the HPG-tree integrates a hyperbolic paraboloid-like framework in its node layout, allowing it to halve the number of index nodes in many cases. This optimization is key to reducing disk or memory scans, thereby accelerating point lookups, range queries, and updates. Our experiments demonstrate that the HPG-tree outperforms comparable state-of-the-art structures like <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i>*-tree, achieving up to a 50% improvement in storage utilization and significant gains in query throughput. HPG-tree opens a promising avenue for modern spatial databases that require both high scalability and sub-second response, making it a robust and flexible option for today’s evolving data-intensive environments. These advantages make HPG-tree particularly well-suited to large-scale spatial databases requiring both high scalability and sub-second responsiveness. Following a detailed discussion of the shortcomings in existing methods, the paper presents the HPG-tree methodology, including its grid partitioning, node layout, and insertion procedures, illustrating why this hybrid strategy stands out as a robust and flexible option for evolving data-intensive environments.