Database Paper Browser

Back to papers

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
8441
Venue
VLDB
Year
1997
Pagerank
7.9364369e-05
Overall Rank
2,905 | 79.82%
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,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,285 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.1097273e-05
2,708 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 8.2643522e-05
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
4,738 Joining Interval Data in Relational Databases 2004 SIGMOD 5.9526916e-05
5,646 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3924438e-05
6,707 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 4.9500448e-05
7,727 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6616221e-05
9,020 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 4.4049428e-05
9,863 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 4.2636378e-05
10,516 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 4.1905499e-05
12,760 Algorithms for Querying by Spatial Structure 1998 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
75 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057450043
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
923 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015254021
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
1,605 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00011180126
4,613 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0427196e-05
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05
4,741 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 5.951386e-05
2,673 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3323551e-05
5,864 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.2947135e-05
7,727 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6616221e-05
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518