Benchmarking Spatial Join Operations with Spatial Output

Summary: Benchmarking spatial join with spatial output across planar line segments; R-tree, R*-tree, R+-tree, PMR quadtree; report build and join times. Disjoint-space decompositions (R+-tree; PMR quadtree) outperform non-disjoint ones (R-tree; R*-tree); PMR scales with output. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8494
Venue: VLDB
Year: 1995
Pagerank: 6.0859946e-05
Overall Rank: 5,795 | 60.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Erik G. Hoelt (Graphic Data Systems Corporation; University of Maryland)
2. Hanan Samet (University of Maryland)

BibTeX Citation

@article{hoelt_vldb95,
        title = {{Benchmarking Spatial Join Operations with Spatial Output}},
        author = {Hoelt, Erik G. and Samet, Hanan},
        journal = {PVLDB},
        series = {{VLDB} '95},
        pages = {606},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
7,070	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.7116663e-05
11,334	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
650	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00015319951
726	Client-Server Paradise	1994	VLDB	0.0001460632
1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.6928497e-05
2,168	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.0469646e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.9227722e-05
7,262	A Population Analysis for Hierarchical Data Structures	1987	SIGMOD	5.6612247e-05
8,796	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.3702721e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
2	4,740	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
3	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
4	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
5	2,168	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD
6	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
8	2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
9	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
10	6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB