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: 8631
Venue: VLDB
Year: 1997
Pagerank: 8.432498e-05
Overall Rank: 2,548 | 82.52%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yun-Wu Huang (International Business Machines T. J. Watson Research Center)
2. Ning Jing (Changsha Institute of Technology)
3. Elke A. Rundensteiner (Worcester Polytechnic Institute)

BibTeX Citation

@article{huang_vldb97,
        title = {{Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations}},
        author = {Huang, Yun-Wu and Jing, Ning and Rundensteiner, Elke A.},
        journal = {PVLDB},
        series = {{VLDB} '97},
        pages = {396},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
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
3,170	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	7.6703896e-05
4,268	Joining Interval Data in Relational Databases	2004	SIGMOD	6.7925685e-05
4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.4949956e-05
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05
5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	6.1351417e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05
9,233	Indexing Medium-dimensionality Data in Oracle	1999	SIGMOD	5.3017497e-05
9,544	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2528121e-05
10,017	Continuous Query Processing in Data Streams Using Duality of Data and Queries	2006	SIGMOD	5.1758281e-05
12,944	Algorithms for Querying by Spatial Structure	1998	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
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
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
2	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
3	5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
4	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
5	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
6	4,740	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
7	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
8	5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
9	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
10	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD