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)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 148 | Efficient Processing of Spatial Joins Using R-trees | 1993 | SIGMOD | 0.00041182766 |
| 925 | Partition Based Spatial-Merge Join | 1996 | SIGMOD | 0.00015264328 |
| 1,174 | Spatial Hash-Joins | 1996 | SIGMOD | 0.00013486418 |
| 2,672 | Spatial Joins Using Seeded Trees | 1994 | SIGMOD | 8.3363695e-05 |
| 3,457 | Size Separation Spatial Join | 1997 | SIGMOD | 7.0755358e-05 |
| 7,332 | The Complexity of Boolean Conjunctive Queries with Intersection Joins | 2022 | PODS | 4.7606012e-05 |
| 7,729 | Processing and Optimization of Multiway Spatial Joins Using R-trees | 1999 | PODS | 4.6660821e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,672 | Spatial Joins Using Seeded Trees | 1994 | SIGMOD | 8.3363695e-05 |
| 8,159 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD | 4.5729025e-05 |
| 3,833 | Output-optimal Parallel Algorithms for Similarity Joins | 2017 | PODS | 6.7173578e-05 |
| 1,174 | Spatial Hash-Joins | 1996 | SIGMOD | 0.00013486418 |
| 6,454 | On Spatially Partitioned Temporal Join | 1994 | VLDB | 5.0569697e-05 |
| 6,500 | Adaptive Multi-Stage Distance Join Processing | 2000 | SIGMOD | 5.0381573e-05 |
| 4,529 | Integration of Spatial Join Algorithms for Processing Multiple Inputs | 1999 | SIGMOD | 6.1078661e-05 |
| 148 | Efficient Processing of Spatial Joins Using R-trees | 1993 | SIGMOD | 0.00041182766 |
| 7,729 | Processing and Optimization of Multiway Spatial Joins Using R-trees | 1999 | PODS | 4.6660821e-05 |
| 478 | Multi-Step Processing of Spatial Joins | 1994 | SIGMOD | 0.0002222104 |