Database Paper Browser

Back to papers

Partition Based Spatial-Merge Join

Summary: PBSM: partition-based spatial-merge join for cases with no input index, using chunked partitions and a plane-sweep. Paradise study compares PBSM with indexed-nested-loops and index-based spatial joins on GIS data, noting clustering and parallelism. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2890
Venue
SIGMOD
Year
1996
Pagerank
0.00015254021
Overall Rank
923 | 93.59%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 37 of 37 citing papers.

Rank Citing Paper Year Venue Pagerank
80 Weaving Relations for Cache Performance 2001 VLDB 0.00055735291
239 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031581944
862 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00015798065
1,043 Set Containment Joins: The Good, The Bad and The Ugly 2000 VLDB 0.00014468616
1,156 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00013606064
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
1,559 Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates 1997 VLDB 0.00011368746
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
2,744 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 8.1917832e-05
2,905 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9364369e-05
3,462 Size Separation Spatial Join 1997 SIGMOD 7.0683581e-05
4,405 Filtering with Approximate Predicates 1998 VLDB 6.2048285e-05
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
4,567 User-Defined Table Operators: Enhancing Extensibility for ORDBMS 1999 VLDB 6.0728188e-05
4,738 Joining Interval Data in Relational Databases 2004 SIGMOD 5.9526916e-05
4,741 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 5.951386e-05
4,778 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 5.9259497e-05
5,523 On Producing Join Results Early 2003 PODS 5.4648346e-05
5,526 GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons 2018 VLDB 5.4585713e-05
5,561 On the Complexity of Join Predicates 2001 PODS 5.4346872e-05
5,646 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3924438e-05
5,985 The Era of Big Spatial Data 2017 VLDB 5.2399365e-05
5,987 External Memory Algorithms 1998 PODS 5.2399221e-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
6,502 Similarity Join over Array Data 2016 SIGMOD 5.0288901e-05
7,113 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 4.8226178e-05
7,328 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 4.7560344e-05
8,260 Raster Intervals: An Approximation Technique for Polygon Intersection Joins 2023 SIGMOD 4.5421134e-05
8,572 THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads 2015 SIGMOD 4.4885798e-05
9,080 AT-GIS: Highly Parallel Spatial Query Processing with Associative Transducers 2016 SIGMOD 4.3956437e-05
10,516 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 4.1905499e-05
10,925 Optimal (Multiway) Spatial Joins 2024 PODS 4.1905499e-05
11,131 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.1905499e-05
12,295 LifeRaft: Data-Driven, Batch Processing for the Exploration of Scientific Databases 2009 CIDR 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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
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
217 A Class of Data Structures for Associative Searching 1984 PODS 0.00033533621
292 Shoring Up Persistent Applications 1994 SIGMOD 0.00028735468
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
548 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00020369531
667 The Sequoia 2000 Storage Benchmark 1993 SIGMOD 0.00018431008
766 Client-Server Paradise 1994 VLDB 0.0001690298
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00014524981
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
1,861 An Adaptive Hash Join Algorithm for Multiuser Environments 1990 VLDB 0.00010297093
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
2,673 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3323551e-05
3,065 Query Processing Method for Multi-Attribute Clustered Relations 1990 VLDB 7.6258862e-05
3,087 The Montage Extensible DataBlade Architecture 1994 SIGMOD 7.5947335e-05
5,864 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.2947135e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,605 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00011180126
862 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00015798065
3,462 Size Separation Spatial Join 1997 SIGMOD 7.0683581e-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
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
6,452 On Spatially Partitioned Temporal Join 1994 VLDB 5.0519322e-05
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
2,119 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.5036401e-05