Database Paper Browser

Back to papers

Scalable Sweeping-Based Spatial Join

Summary: SSSJ for the filter step with unindexed inputs; robust to skew and worst-case data. Combines distribution-sweeping with optimized in-memory plane-sweep to achieve near-optimal I/O, with comparison to PBSM. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8520
Venue
VLDB
Year
1998
Pagerank
9.5547223e-05
Overall Rank
2,094 | 85.44%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
389 Query Processing in Spatial Network Databases 2003 VLDB 0.00024620268
4,529 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.1078661e-05
4,737 Joining Interval Data in Relational Databases 2004 SIGMOD 5.9604127e-05
4,746 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 5.9571146e-05
4,780 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 5.9263494e-05
5,511 On Producing Join Results Early 2003 PODS 5.4699346e-05
5,979 External Memory Algorithms 1998 PODS 5.2450009e-05
6,154 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.1815134e-05
6,161 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.1753664e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
7,332 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 4.7606012e-05
7,616 SkyQuery: A Web Service Approach to Federate Databases 2003 CIDR 4.6945188e-05
8,159 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 4.5729025e-05
8,263 Raster Intervals: An Approximation Technique for Polygon Intersection Joins 2023 SIGMOD 4.5464722e-05
8,868 A Bayesian Method for Guessing the Extreme Values in a Data Set 2007 VLDB 4.4320869e-05
11,106 QPJVis Demo: Quality-boost Progressive Join Query Processing System 2024 VLDB 4.1945683e-05
11,334 SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization 2022 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
76 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057303551
84 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053866006
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
236 High-Performance Sorting on Networks of Workstations 1997 SIGMOD 0.00031779642
925 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015264328
1,034 Redundancy in Spatial Databases 1989 SIGMOD 0.00014534274
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013486418
1,997 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8322994e-05
2,414 A Super Scalar Sort Algorithm for RISC Processors 1996 SIGMOD 8.8659979e-05
2,472 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.7237893e-05
2,672 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3363695e-05
2,900 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9405413e-05
3,083 The Montage Extensible DataBlade Architecture 1994 SIGMOD 7.6013368e-05
3,457 Size Separation Spatial Join 1997 SIGMOD 7.0755358e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
3,571 Lightning Fast and Space Efficient Inequality Joins 2015 VLDB 6.9580858e-05
4,612 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0484423e-05
5,960 Skew-Aware Join Optimization for Array Databases 2015 SIGMOD 5.2559595e-05
10,921 Optimal (Multiway) Spatial Joins 2024 PODS 4.1945683e-05
925 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015264328
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013486418
4,529 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.1078661e-05
6,154 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.1815134e-05
3,457 Size Separation Spatial Join 1997 SIGMOD 7.0755358e-05