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: h54a72c08f741540f
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014239937
Overall Rank: 752 | 94.95%
DOI: 10.1145/233269.233338

Incoming Non-self Citations Over Time

Authors

1. Jignesh M. Patel (University of Wisconsin)
2. David J. DeWitt (University of Wisconsin)

BibTeX Citation

@inproceedings{patel_sigmod96,
        title = {{Partition Based Spatial-Merge Join}},
        author = {Patel, Jignesh M. and DeWitt, David J.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233338},
        url = {https://dl.acm.org/doi/10.1145/233269.233338},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 37 of 37 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043795812
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
994	Spatial Hash-Joins	1996	SIGMOD	0.00012630797
1,171	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011697392
1,229	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00011421502
1,547	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010289422
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010129129
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,589	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2479257e-05
2,912	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8683521e-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
4,336	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6528595e-05
4,479	Filtering with Approximate Predicates	1998	VLDB	6.5797399e-05
4,728	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.4446427e-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,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,609	On Producing Join Results Early	2003	PODS	6.0665543e-05
6,054	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.9000316e-05
6,151	Similarity Join over Array Data	2016	SIGMOD	5.8678874e-05
6,416	External Memory Algorithms	1998	PODS	5.7904533e-05
6,463	The Era of Big Spatial Data	2017	VLDB	5.7741601e-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,615	On the Complexity of Join Predicates	2001	PODS	5.4823519e-05
8,231	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.3717128e-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
9,292	AT-GIS: Highly Parallel Spatial Query Processing with Associative Transducers	2016	SIGMOD	5.2008018e-05
11,495	Optimal (Multiway) Spatial Joins	2024	PODS	4.9769913e-05
11,658	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.9769913e-05
12,779	LifeRaft: Data-Driven, Batch Processing for the Exploration of Scientific Databases	2009	CIDR	4.9769913e-05

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.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
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029048509
265	A Class of Data Structures for Associative Searching	1984	PODS	0.00022748432
302	Shoring Up Persistent Applications	1994	SIGMOD	0.00021664369
490	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017433989
527	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016874202
667	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00014983804
744	Client-Server Paradise	1994	VLDB	0.00014305129
994	Spatial Hash-Joins	1996	SIGMOD	0.00012630797
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012388306
1,799	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB	9.611163e-05
1,862	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.4827102e-05
2,298	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.6797199e-05
2,359	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.5776736e-05
3,072	The Montage Extensible DataBlade Architecture	1994	SIGMOD	7.6777206e-05
3,843	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	6.9863511e-05
5,908	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.9480991e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
2	1,547	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD
3	3,122	Size Separation Spatial Join	1997	SIGMOD
4	2,359	Spatial Joins Using Seeded Trees	1994	SIGMOD
5	5,908	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
6	527	Multi-Step Processing of Spatial Joins	1994	SIGMOD
7	994	Spatial Hash-Joins	1996	SIGMOD
8	6,290	On Spatially Partitioned Temporal Join	1994	VLDB
9	4,928	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	1,924	Scalable Sweeping-Based Spatial Join	1998	VLDB