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.0001419395
Overall Rank: 760 | 94.91%
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.00043770511
180	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026534482
999	Spatial Hash-Joins	1996	SIGMOD	0.00012590189
1,173	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011659702
1,235	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00011384515
1,549	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010257684
1,598	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010096339
1,930	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3453623e-05
2,007	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.182637e-05
2,597	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2212352e-05
2,923	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8423791e-05
3,131	Size Separation Spatial Join	1997	SIGMOD	7.6016052e-05
3,232	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	7.4890975e-05
4,350	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6363233e-05
4,495	Filtering with Approximate Predicates	1998	VLDB	6.5601814e-05
4,746	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.4264234e-05
4,863	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	6.3631681e-05
4,954	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.3263552e-05
4,980	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.3167773e-05
5,492	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	6.0966695e-05
5,547	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0715188e-05
5,620	On Producing Join Results Early	2003	PODS	6.0466546e-05
6,068	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.8805774e-05
6,168	Similarity Join over Array Data	2016	SIGMOD	5.8484846e-05
6,427	External Memory Algorithms	1998	PODS	5.7713075e-05
6,476	The Era of Big Spatial Data	2017	VLDB	5.7551052e-05
6,552	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7306642e-05
6,979	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6129856e-05
7,491	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.4981344e-05
7,630	On the Complexity of Join Predicates	2001	PODS	5.4642768e-05
8,249	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.3539505e-05
8,683	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2733366e-05
8,829	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2533436e-05
9,316	AT-GIS: Highly Parallel Spatial Query Processing with Associative Transducers	2016	SIGMOD	5.1836101e-05
11,547	Optimal (Multiway) Spatial Joins	2024	PODS	4.9605343e-05
11,705	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.9605343e-05
12,822	LifeRaft: Data-Driven, Batch Processing for the Exploration of Scientific Databases	2009	CIDR	4.9605343e-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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
102	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033850505
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
267	A Class of Data Structures for Associative Searching	1984	PODS	0.00022688423
302	Shoring Up Persistent Applications	1994	SIGMOD	0.00021600053
491	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017383221
530	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016832286
668	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00014936842
747	Client-Server Paradise	1994	VLDB	0.00014259869
999	Spatial Hash-Joins	1996	SIGMOD	0.00012590189
1,038	Redundancy in Spatial Databases	1989	SIGMOD	0.00012349149
1,808	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB	9.5852314e-05
1,869	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.4516156e-05
2,307	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.6516423e-05
2,368	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.5495935e-05
3,080	The Montage Extensible DataBlade Architecture	1994	SIGMOD	7.6526762e-05
3,851	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	6.9637995e-05
5,921	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.9284908e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
2	1,549	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD
3	3,131	Size Separation Spatial Join	1997	SIGMOD
4	2,368	Spatial Joins Using Seeded Trees	1994	SIGMOD
5	5,921	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
6	530	Multi-Step Processing of Spatial Joins	1994	SIGMOD
7	999	Spatial Hash-Joins	1996	SIGMOD
8	6,286	On Spatially Partitioned Temporal Join	1994	VLDB
9	4,954	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	1,930	Scalable Sweeping-Based Spatial Join	1998	VLDB