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 |
|---|---|---|---|---|
| 147 | Efficient Processing of Spatial Joins Using R-trees | 1993 | SIGMOD | 0.00041201518 |
| 923 | Partition Based Spatial-Merge Join | 1996 | SIGMOD | 0.00015254021 |
| 1,174 | Spatial Hash-Joins | 1996 | SIGMOD | 0.00013490827 |
| 2,673 | Spatial Joins Using Seeded Trees | 1994 | SIGMOD | 8.3323551e-05 |
| 3,462 | Size Separation Spatial Join | 1997 | SIGMOD | 7.0683581e-05 |
| 7,328 | The Complexity of Boolean Conjunctive Queries with Intersection Joins | 2022 | PODS | 4.7560344e-05 |
| 7,727 | Processing and Optimization of Multiway Spatial Joins Using R-trees | 1999 | PODS | 4.6616221e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,673 | Spatial Joins Using Seeded Trees | 1994 | SIGMOD | 8.3323551e-05 |
| 8,163 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD | 4.5685178e-05 |
| 3,831 | Output-optimal Parallel Algorithms for Similarity Joins | 2017 | PODS | 6.7146681e-05 |
| 1,174 | Spatial Hash-Joins | 1996 | SIGMOD | 0.00013490827 |
| 6,496 | Adaptive Multi-Stage Distance Join Processing | 2000 | SIGMOD | 5.0327729e-05 |
| 6,452 | On Spatially Partitioned Temporal Join | 1994 | VLDB | 5.0519322e-05 |
| 4,539 | Integration of Spatial Join Algorithms for Processing Multiple Inputs | 1999 | SIGMOD | 6.0982886e-05 |
| 147 | Efficient Processing of Spatial Joins Using R-trees | 1993 | SIGMOD | 0.00041201518 |
| 7,727 | Processing and Optimization of Multiway Spatial Joins Using R-trees | 1999 | PODS | 4.6616221e-05 |
| 479 | Multi-Step Processing of Spatial Joins | 1994 | SIGMOD | 0.00022182486 |