Spatial Joins Using Seeded Trees

Summary: Join-time seeded trees (R-tree-like) enable spatial joins without prebuilt indices; supports multi-layer overlays and non-spatial selections. Seed levels guide growth and filter data to shrink the structure; linked-list construction reduces random I/Os to sequential, delivering major I/O gains and generally lower CPU cost (except with seed filtering). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2727
Venue: SIGMOD
Year: 1994
Pagerank: 8.3363695e-05
Overall Rank: 2,672 | 81.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ming-Ling Lo
2. Chinya V. Ravishankar

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-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,860	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2990241e-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,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05
10,921	Optimal (Multiway) Spatial Joins	2024	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
1,034	Redundancy in Spatial Databases	1989	SIGMOD	0.00014534274
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05
2,472	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7237893e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,500	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0381573e-05
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
5,860	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2990241e-05
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
2,900	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	7.9405413e-05
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766