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: 3019
Venue: SIGMOD
Year: 1997
Pagerank: 7.7941163e-05
Overall Rank: 3,066 | 78.97%
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
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
1,993	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.3421788e-05
4,482	Overlap Interval Partition Join	2014	SIGMOD	6.6753072e-05
4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.4949956e-05
4,844	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.4826356e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.6435709e-05
7,451	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6135032e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
11,141	Optimal (Multiway) Spatial Joins	2024	PODS	5.093636e-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.0020210012
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.3194496e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,172	On Spatially Partitioned Temporal Join	1994	VLDB
2	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
3	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
4	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
5	5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
6	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
7	994	Spatial Hash-Joins	1996	SIGMOD
8	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
9	1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB
10	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD