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.00014246504
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.00043805923
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,171	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011702886
1,227	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.000114264
1,546	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010294163
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010133792
1,922	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3751198e-05
1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.216723e-05
2,588	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2518251e-05
2,911	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8720638e-05
3,120	Size Separation Spatial Join	1997	SIGMOD	7.6300049e-05
3,221	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	7.5149339e-05
4,336	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6560067e-05
4,481	Filtering with Approximate Predicates	1998	VLDB	6.5807146e-05
4,726	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.4476785e-05
4,837	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	6.3872905e-05
4,927	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.3503189e-05
4,956	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.340462e-05
5,467	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	6.119722e-05
5,532	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0932822e-05
5,608	On Producing Join Results Early	2003	PODS	6.0692914e-05
6,052	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.9028248e-05
6,149	Similarity Join over Array Data	2016	SIGMOD	5.8706665e-05
6,413	External Memory Algorithms	1998	PODS	5.7931958e-05
6,461	The Era of Big Spatial Data	2017	VLDB	5.7768622e-05
6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7523628e-05
6,955	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6342744e-05
7,468	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.5189807e-05
7,608	On the Complexity of Join Predicates	2001	PODS	5.4849468e-05
8,225	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.3742569e-05
8,658	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2933372e-05
8,804	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2732683e-05
9,283	AT-GIS: Highly Parallel Spatial Query Processing with Associative Transducers	2016	SIGMOD	5.203265e-05
11,489	Optimal (Multiway) Spatial Joins	2024	PODS	4.9793485e-05
11,652	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.9793485e-05
12,773	LifeRaft: Data-Driven, Batch Processing for the Exploration of Scientific Databases	2009	CIDR	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
302	Shoring Up Persistent Applications	1994	SIGMOD	0.0002167061
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
527	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016880616
665	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00014990574
743	Client-Server Paradise	1994	VLDB	0.00014311524
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
1,799	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB	9.6155018e-05
1,861	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.4871409e-05
2,294	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.6837534e-05
2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.5817166e-05
3,070	The Montage Extensible DataBlade Architecture	1994	SIGMOD	7.6813274e-05
3,842	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	6.9896266e-05
5,905	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.9509027e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
2	1,546	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD
3	3,120	Size Separation Spatial Join	1997	SIGMOD
4	2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD
5	5,905	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,287	On Spatially Partitioned Temporal Join	1994	VLDB
9	4,927	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	1,922	Scalable Sweeping-Based Spatial Join	1998	VLDB