Optimal (Multiway) Spatial Joins

Summary: Report all k-tuples of axis-aligned rectangles from R1,...,Rk with nonempty intersection in 2D. Achieves O(n log n + OUT) time independent of k (for constant k), matching the comparison-based lower bound and outperforming the prior O(n log^{2k-1} n + OUT). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1978
Venue: PODS
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,141 | 23.57%
DOI: 10.1145/3695828

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Ru Wang (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{wang_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Optimal (Multiway) Spatial Joins}},
        url = {https://dl.acm.org/doi/10.1145/3695828},
        doi = {10.1145/3695828},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Wang, Ru and Tao, Yufei},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
7,451	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6135032e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
2	8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD
3	2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
4	994	Spatial Hash-Joins	1996	SIGMOD
5	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
6	6,172	On Spatially Partitioned Temporal Join	1994	VLDB
7	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
8	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
9	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
10	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD