Data-Parallel Spatial Join Algorithms
Erik G. Hoel, Hanan Samet · 1994
Efficient data-parallel spatial join algorithms for bucket PMR quadtrees and R-trees, common spatial data structures, are given. The domain consists of planar line segment data (i.e., Bureau of the Census TIGER/Line files). Parallel algorithms for map intersection and a spatial range query are described. The algorithms are implemented using the scan model of parallel computation on the hypercube architecture of the Connection Machine.