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: 2728
Venue: SIGMOD
Year: 1994
Pagerank: 8.3323551e-05
Overall Rank: 2,673 | 81.43%
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
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-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,864	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2947135e-05
6,170	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.1708554e-05
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-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
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00014524981
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05
2,471	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7158825e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-05
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
5,864	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2947135e-05
4,613	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0427196e-05
2,905	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	7.9364369e-05
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05
4,539	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.0982886e-05
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518