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: 2951
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014542772
Overall Rank: 728 | 95.01%
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
49	Weaving Relations for Cache Performance	2001	VLDB	0.00043781096
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,151	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011938186
1,201	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00011674339
1,517	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010520118
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
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
2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.432498e-05
2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	8.0383547e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-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,435	Filtering with Approximate Predicates	1998	VLDB	6.7078883e-05
4,645	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.5900051e-05
4,740	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	6.5283833e-05
4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.4949956e-05
4,844	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.4826356e-05
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05
5,467	On Producing Join Results Early	2003	PODS	6.2074577e-05
5,709	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	6.1142154e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
6,157	Similarity Join over Array Data	2016	SIGMOD	5.9554363e-05
6,289	External Memory Algorithms	1998	PODS	5.9261616e-05
6,382	The Era of Big Spatial Data	2017	VLDB	5.8915267e-05
6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.8809448e-05
7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.6435709e-05
7,451	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6135032e-05
7,467	On the Complexity of Join Predicates	2001	PODS	5.6103871e-05
8,061	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.4953977e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
9,117	AT-GIS: Highly Parallel Spatial Query Processing with Associative Transducers	2016	SIGMOD	5.3204028e-05
9,544	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2528121e-05
11,141	Optimal (Multiway) Spatial Joins	2024	PODS	5.093636e-05
11,334	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	5.093636e-05
12,482	LifeRaft: Data-Driven, Batch Processing for the Exploration of Scientific Databases	2009	CIDR	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
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
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
299	Shoring Up Persistent Applications	1994	SIGMOD	0.00022084669
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
650	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00015319951
726	Client-Server Paradise	1994	VLDB	0.0001460632
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,779	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB	9.7764427e-05
1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.6928497e-05
2,249	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.8700017e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
3,010	The Montage Extensible DataBlade Architecture	1994	SIGMOD	7.8538236e-05
3,771	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.1391812e-05
5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	6.0859946e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
2	1,517	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD
3	3,066	Size Separation Spatial Join	1997	SIGMOD
4	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
5	5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
6	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
7	994	Spatial Hash-Joins	1996	SIGMOD
8	6,172	On Spatially Partitioned Temporal Join	1994	VLDB
9	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB