Processing and Optimization of Multiway Spatial Joins Using R-trees

Summary: Systematic search algorithms that exploit R-tree hierarchies to directly evaluate multiway spatial joins without building temporary indexes or materializing intermediates. Proposes cost models and an optimizer for search ordering, validated by extensive experiments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1159
Venue: PODS
Year: 1999
Pagerank: 5.5541724e-05
Overall Rank: 7,744 | 46.87%
DOI: 10.1145/303976.303981

Incoming Non-self Citations Over Time

Authors

1. Dimitris Papadias (Hong Kong University of Science and Technology)
2. Nikos Mamoulis (Hong Kong University of Science and Technology)
3. Yannis Theodoridis (Computer Technology Institute)

BibTeX Citation

@inproceedings{papadias_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Processing and Optimization of Multiway Spatial Joins Using R-trees}},
        url = {https://dl.acm.org/doi/10.1145/303976.303981},
        doi = {10.1145/303976.303981},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Papadias, Dimitris and Mamoulis, Nikos and Theodoridis, Yannis},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010017073
4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.4949956e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
11,141	Optimal (Multiway) Spatial Joins	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
708	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014727576
1,373	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001098638
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
2,341	Parallel R-trees	1992	SIGMOD	8.7233426e-05
2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.432498e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.4949956e-05
9,099	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	5.3250598e-05
12,944	Algorithms for Querying by Spatial Structure	1998	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,290	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD
2	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
3	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
4	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD
5	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
6	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
7	2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
8	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
9	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD