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: hfacd11beaa6ed19c
Venue: SIGMOD
Year: 1997
Pagerank: 7.6016052e-05
Overall Rank: 3,131 | 79.02%
DOI: 10.1145/253260.253340

Incoming Non-self Citations Over Time

Authors

1. Nick Koudas (University of Toronto)
2. Kenneth C. Sevcik (University of Toronto)

BibTeX Citation

@inproceedings{koudas_sigmod97,
        title = {{Size Separation Spatial Join}},
        author = {Koudas, Nick and Sevcik, Kenneth C.},
        series = {{SIGMOD} '97},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/253260.253340},
        url = {https://dl.acm.org/doi/10.1145/253260.253340},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
180	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026534482
1,930	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3453623e-05
2,007	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.182637e-05
4,578	Overlap Interval Partition Join	2014	SIGMOD	6.5107046e-05
4,954	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.3263552e-05
4,980	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.3167773e-05
6,068	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.8805774e-05
6,979	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6129856e-05
7,491	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.4981344e-05
7,924	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4090777e-05
8,683	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2733366e-05
11,547	Optimal (Multiway) Spatial Joins	2024	PODS	4.9605343e-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.0019892478
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045231517
102	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033850505
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
530	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016832286
760	Partition Based Spatial-Merge Join	1996	SIGMOD	0.0001419395
999	Spatial Hash-Joins	1996	SIGMOD	0.00012590189
5,350	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.1545256e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,286	On Spatially Partitioned Temporal Join	1994	VLDB
2	1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
3	11,547	Optimal (Multiway) Spatial Joins	2024	PODS
4	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
5	5,350	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
6	530	Multi-Step Processing of Spatial Joins	1994	SIGMOD
7	999	Spatial Hash-Joins	1996	SIGMOD
8	2,368	Spatial Joins Using Seeded Trees	1994	SIGMOD
9	1,930	Scalable Sweeping-Based Spatial Join	1998	VLDB
10	4,954	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD