Performance of Data-Parallel Spatial Operations

Summary: Data-parallel spatial ops (build, polygonization, spatial join) for planar line segments compare bucket PMR quadtree, R-tree, and R+-tree on the Connection Machine. Bucket PMR quadtree outperforms the others due to a regular disjoint space decomposition that boosts parallelism and reduces interprocessor communication. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc7fbc0379d5efd2d
Venue: VLDB
Year: 1994
Pagerank: 5.7688769e-05
Overall Rank: 6,431 | 56.90%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Erik G. Hoelt (United States Census Bureau)
2. Hanan Samet (University of Maryland)

BibTeX Citation

@article{hoelt_vldb94,
        title = {{Performance of Data-Parallel Spatial Operations}},
        author = {Hoelt, Erik G. and Samet, Hanan},
        journal = {PVLDB},
        series = {{VLDB} '94},
        pages = {156},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,239	Spatial Partitioning Techniques in SpatialHadoop	2015	VLDB	6.7011937e-05
5,921	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.9284908e-05
8,834	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.2524856e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
55	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00040385073
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
194	Data Placement In Bubba	1988	SIGMOD	0.00025627096
1,869	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.4516156e-05
2,217	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	8.8230488e-05
2,400	Parallel R-trees	1992	SIGMOD	8.5059093e-05
2,659	A Performance Analysis of Alternative Multi-Attribute Declustering Strategies	1992	SIGMOD	8.1438661e-05
6,610	Research Directions in Object-Oriented Database Systems	1990	PODS	5.7180274e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,761	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
2	4,863	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
3	5,350	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
4	6,231	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
5	2,597	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
6	12,032	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
7	2,217	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD
8	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
9	2,400	Parallel R-trees	1992	SIGMOD
10	5,921	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB