Multi-Step Processing of Spatial Joins

Summary: Three-step spatial join for extended 2D objects: MBR-based candidate generation, pruning via conservative/progressive approximations, then exact geometry tests. In-memory, componentwise decomposition of objects into simple parts organized by a main-memory spatial structure yields substantial gains on real cartographic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2727
Venue: SIGMOD
Year: 1994
Pagerank: 0.00022182486
Overall Rank: 479 | 96.68%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
80	Weaving Relations for Cache Performance	2001	VLDB	0.00055735291
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031093647
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
471	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00022348285
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010661725
1,987	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.8561164e-05
2,283	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD	9.1138663e-05
2,708	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	8.2643522e-05
2,767	Hardware Acceleration in Commercial Databases: A Case Study of Spatial Operations	2004	VLDB	8.1550146e-05
3,111	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.5445257e-05
3,462	Size Separation Spatial Join	1997	SIGMOD	7.0683581e-05
5,864	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2947135e-05
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-05
8,260	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	4.5421134e-05
8,599	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4832771e-05
8,866	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	4.4281817e-05
10,516	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	4.1905499e-05
12,760	Algorithms for Querying by Spatial Structure	1998	VLDB	4.1905499e-05
14,128	GENESYS: A System for Efficient Spatial Query Processing	1994	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
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
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028845557
8,599	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4832771e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
2,905	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	7.9364369e-05
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
4,741	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	5.951386e-05
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-05
2,283	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD	9.1138663e-05
4,539	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.0982886e-05
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05