Size Separation Spatial Join

Summary: Proposes Size Separation Spatial Join (S3J), a no-index, no-replication, hierarchical space-division algorithm; runtime scales with input sizes. DSB enables dynamic bitmap-style processing; offers simple cost models and empirical gains over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2958
Venue: SIGMOD
Year: 1997
Pagerank: 7.0683581e-05
Overall Rank: 3,462 | 75.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Nick Koudas
2. Kenneth C. Sevcik

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,285	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1097273e-05
4,539	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.0982886e-05
4,778	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	5.9259497e-05
5,197	Overlap Interval Partition Join	2014	SIGMOD	5.6308314e-05
6,170	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.1708554e-05
7,113	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	4.8226178e-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
8,572	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4885798e-05
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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.0032118946
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
4,613	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0427196e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,452	On Spatially Partitioned Temporal Join	1994	VLDB	5.0519322e-05
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
4,613	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0427196e-05
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
4,539	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.0982886e-05