Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations

Summary: Introduces BFRJ, a breadth-first, synchronized R-tree join across two trees. Per level, it builds a join index and applies global optimizations to accelerate the next level, yielding up to 50% gains vs the state of the art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8440
Venue: VLDB
Year: 1997
Pagerank: 7.9405413e-05
Overall Rank: 2,900 | 79.83%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,281	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1077704e-05
2,703	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	8.2722965e-05
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05
4,737	Joining Interval Data in Relational Databases	2004	SIGMOD	5.9604127e-05
5,636	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	5.3981191e-05
6,705	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9549359e-05
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05
9,017	Indexing Medium-dimensionality Data in Oracle	1999	SIGMOD	4.4091374e-05
9,864	Continuous Query Processing in Data Streams Using Duality of Data and Queries	2006	SIGMOD	4.2675822e-05
10,507	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	4.1945683e-05
12,751	Algorithms for Querying by Spatial Structure	1998	VLDB	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
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
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
6,500	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0381573e-05
4,746	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	5.9571146e-05
2,672	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3363695e-05
5,860	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2990241e-05
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766