DBScholar

Back to papers

Efficient Processing of Spatial Joins Using R-trees

Summary: First detailed study of spatial join processing using R*-trees at scale, addressing CPU and I/O bottlenecks. Techniques yield order-of-magnitude speedup over naive approaches; buffering makes I/O near-optimal, validated on large real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
ha227dabc9d575d27
Venue
SIGMOD
Year
1993
Pagerank
0.00029048509
Overall Rank
146 | 99.03%
DOI
10.1145/170035.170075

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{brinkhoff_sigmod93,
        title = {{Efficient Processing of Spatial Joins Using R-trees}},
        author = {Brinkhoff, Thomas and Kriegel, Hans-Peter and Seeger, Bernhard},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170075},
        url = {https://dl.acm.org/doi/10.1145/170035.170075},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 60 citing papers.

Rank Citing Paper Year Venue Pagerank
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
94 Efficient and Effective Clustering Methods for Spatial Data Mining 1994 VLDB 0.0003456395
385 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019456733
459 Query Processing in Spatial Network Databases 2003 VLDB 0.00017860573
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017451091
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016874202
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016599925
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014239937
784 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014015324
994 Spatial Hash-Joins 1996 SIGMOD 0.00012630797
1,229 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00011421502
1,552 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010270215
1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010265572
1,594 Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates 1997 VLDB 0.00010129129
1,721 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.792994e-05
1,924 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3706925e-05
1,998 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.2123795e-05
2,359 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5776736e-05
2,589 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.2479257e-05
2,945 Spatio-Textual Similarity Joins 2013 VLDB 7.8244366e-05
3,122 Size Separation Spatial Join 1997 SIGMOD 7.6263979e-05
3,223 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 7.5114215e-05
3,567 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD 7.1981877e-05
3,659 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.1210394e-05
3,910 FALCON: Feedback Adaptive Loop for Content-Based Retrieval 2000 VLDB 6.9284024e-05
4,336 Joining Interval Data in Relational Databases 2004 SIGMOD 6.6528595e-05
4,840 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 6.3842693e-05
4,928 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3473148e-05
4,958 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.3374701e-05
5,334 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1749174e-05
5,472 GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons 2018 VLDB 6.1168576e-05
5,536 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0904184e-05
5,908 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.9480991e-05
6,054 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9000316e-05
6,226 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.8430153e-05
6,350 Clue-based Spatio-textual Query 2017 VLDB 5.8064898e-05
6,420 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.7879896e-05
6,542 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7496415e-05
6,958 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6316072e-05
7,472 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 5.5163696e-05
7,566 Cache-oblivious High-performance Similarity Join 2019 SIGMOD 5.4936211e-05
7,616 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4822011e-05
7,908 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4270211e-05
7,913 SkyQuery: A Web Service Approach to Federate Databases 2003 CIDR 5.4259499e-05
8,231 Raster Intervals: An Approximation Technique for Polygon Intersection Joins 2023 SIGMOD 5.3717128e-05
8,374 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3425405e-05
8,416 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 5.3341916e-05
8,666 THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads 2015 SIGMOD 5.2908314e-05
8,812 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.270772e-05
8,970 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.2473594e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
101 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033923053
265 A Class of Data Structures for Associative Searching 1984 PODS 0.00022748432
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00012388306
2,206 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 8.8514881e-05
2,390 Parallel R-trees 1992 SIGMOD 8.5335833e-05
3,843 Query Processing Method for Multi-Attribute Clustered Relations 1990 VLDB 6.9863511e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,035 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
2 527 Multi-Step Processing of Spatial Joins 1994 SIGMOD
3 4,840 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB
4 9,514 Main-Memory Operation Buffering for Efficient R-Tree Update 2007 VLDB
5 11,495 Optimal (Multiway) Spatial Joins 2024 PODS
6 6,542 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD
7 5,908 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB
8 2,359 Spatial Joins Using Seeded Trees 1994 SIGMOD
9 2,589 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB
10 7,908 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS