Parallel Dynamic Spatial Indexes
Abstract
Maintaining spatial data (points in two or three dimensions) is crucial and has a wide range of applications, such as graphics, GIS, and robotics. To handle spatial data, many data structures, called spatial indexes, have been proposed, e.g. kd-trees, oct/quadtrees (also called Orth-trees), R-trees, and bounding volume hierarchies (BVHs). In real-world applications, spatial datasets tend to be highly dynamic, requiring batch updates of points with low latency. This calls for efficient parallel batch updates on spatial indexes. Unfortunately, there is very little work that achieves this.
Fields of Study & Subjects
Data Management and Algorithms
Advanced Database Systems and Queries
Geographic Information Systems Studies
Publication details
- Journal / source
- Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming
- Publisher
- ACM
- Pages
- 150–163
- Publication date
- 28 January 2026