Parallel Dynamic Spatial Indexes

Ziyang Men, Bo Huang, Yan Gu, Yihan SunPPoPP 2026 · DOI

TL;DR

This paper introduces two novel parallel spatial index structures, P-Orth trees and SPaC-trees, designed for highly dynamic datasets. These structures offer significantly faster batch updates and competitive query performance compared to existing methods, making them ideal for applications with frequent data changes.

What Problem Does This Paper Address?

Maintaining and querying spatial data (points in 2D or 3D) is crucial for applications like GIS, computer graphics, and robotics. While many spatial indexes exist (e.g., kd-trees, R-trees, Orth-trees), real-world datasets are often highly dynamic, requiring efficient handling of frequent batch updates with low latency. Existing parallel spatial indexes struggle with these dynamic workloads, either offering poor update performance or sacrificing query efficiency. This paper aims to bridge this gap by developing parallel spatial indexes that excel at high-throughput updates while maintaining strong query capabilities.

Methods

The authors propose two main data structures:

  • P-Orth Tree: This is a parallel version of Orth-trees (also known as quadtrees/octrees). Unlike previous approaches that rely on space-filling curves (SFCs) for efficiency, the P-Orth tree avoids SFCs entirely. It achieves I/O-efficient construction and batch updates by borrowing the "sieving" algorithm from parallel kd-trees, which reorders points to group them into buckets without explicit SFC computation. This design offers better theoretical bounds for updates and is more flexible with coordinate types.
  • SPaC-Tree Family: This is a parallel R-tree/bounding volume hierarchy (BVH) structure. It builds upon the PaC-tree, a parallel balanced binary search tree, but with key modifications to handle spatial data more effectively. The core innovation is relaxing the strict ordering of points within leaf nodes during batch updates. This "partial order" approach significantly speeds up updates without substantially impacting query performance, a common issue with SFC-based R-trees. The SPaC-tree family includes variants using both Morton (SPaC-Z) and Hilbert (SPaC-H) curves.

Datasets

The authors evaluate their proposed structures using:

  • Synthetic Datasets: These datasets feature various distributions for points, queries, and update patterns, including Uniform, Sweepline, and Varden. The Varden dataset is specifically designed to simulate skewed point distributions.
  • Real-World Datasets: The paper uses the COSMO dataset (3D, clustered) and the OpenStreetMap (OSM) dataset (2D, highly clustered) for Northern America.

Key Insights and Ideas

  • Avoiding SFCs for P-Orth Trees: The paper demonstrates that SFCs, while common in parallel Orth-trees, introduce overheads in computation and data movement. Their P-Orth tree shows that efficient parallel updates can be achieved without them, leading to better performance and flexibility.
  • Partial Order for SPaC-Trees: The most significant insight for SPaC-trees is that strict ordering of points within leaf nodes is not essential for spatial queries but is a bottleneck for batch updates. By relaxing this ordering, they achieve dramatic speedups in updates.
  • Query-Update Tradeoff: The research provides a comprehensive comparison of various parallel spatial indexes, highlighting the inherent trade-offs between query performance and update efficiency. SPaC-trees offer the best update performance, while P-Orth trees strike a strong balance, and Pkd-trees excel in queries but lag in updates.
  • Scalability of SPaC-Trees: The SPaC-tree family exhibits excellent parallel scalability, with SPaC-H-tree showing particularly strong speedups as more cores are utilized.

Key Results

  • Update Performance: SPaC-trees are significantly faster than baselines like Pkd-trees and Zd-trees for batch updates, with SPaC-H-tree being up to 7.5x faster than Pkd-trees. P-Orth trees also offer substantial speedups over Pkd-trees (up to 7.18x).
  • Construction Performance: SPaC-trees are the fastest for construction across all workloads, outperforming baselines by a notable margin. P-Orth trees are competitive, especially on non-skewed data.
  • Query Performance: P-Orth trees generally offer the best or near-best query performance, especially on non-skewed data. SPaC-H-trees are more efficient in queries than SPaC-Z-trees due to Hilbert curve's better locality. Pkd-trees remain strong contenders for query performance, particularly for in-distribution queries.
  • 3D Performance: SPaC-H-trees show good performance in 3D, outperforming P-Orth and Pkd-trees, as SFC-based indexes are less sensitive to dimensionality.
  • Real-World Data: SPaC-trees demonstrate even greater advantages on real-world, highly clustered datasets for construction and updates.

Limitations and Future Work

  • Limitations:
    • The paper notes that P-Orth trees are more affected by skewed data distributions compared to comparison-based indexes like Pkd-trees.
  • SPaC-trees, while excellent for updates, generally have slower query performance than space-partitioning trees like Pkd-trees and P-Orth trees due to overlapping bounding boxes.
  • The theoretical analysis for SPaC-trees relies on the analysis of PaC-trees.
  • Future Work:
    • The authors suggest that the SPaC-tree's ability to handle unsorted leaves could be further explored for other spatial data structures.
  • The paper implicitly suggests that further research into optimizing the query performance of SPaC-trees while maintaining their update efficiency would be valuable.

Summary updated

BibTeX
@inproceedings{men2026parallel,
  author = {Ziyang Men and Bo Huang and Yan Gu and Yihan Sun},
  title = {{Parallel Dynamic Spatial Indexes}},
  booktitle = {PPoPP},
  year = {2026},
  doi = {10.1145/3774934.3786412},
}

Loading related content...

Figure