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: 2957
Venue: SIGMOD
Year: 1997
Pagerank: 7.0755358e-05
Overall Rank: 3,457 | 75.96%
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
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
2,281	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1077704e-05
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05
4,780	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	5.9263494e-05
5,190	Overlap Interval Partition Join	2014	SIGMOD	5.6381091e-05
6,161	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.1753664e-05
7,133	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	4.8226285e-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
8,575	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4928872e-05
10,921	Optimal (Multiway) Spatial Joins	2024	PODS	4.1945683e-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.0032169493
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
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,454	On Spatially Partitioned Temporal Join	1994	VLDB	5.0569697e-05
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
10,921	Optimal (Multiway) Spatial Joins	2024	PODS	4.1945683e-05
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
2,672	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3363695e-05
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05