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: h0e08850e60889be3
Venue: SIGMOD
Year: 1994
Pagerank: 0.00016880616
Overall Rank: 527 | 96.46%
DOI: 10.1145/191839.191880

Incoming Non-self Citations Over Time

Authors

1. Thomas Brinkhoff (University of Munich)
2. Hans-Peter Kriegel (University of Munich)
3. Ralf Schneider (University of Munich)
4. Bernhard Seeger (University of Munich)

BibTeX Citation

@inproceedings{brinkhoff_sigmod94,
        title = {{Multi-Step Processing of Spatial Joins}},
        author = {Brinkhoff, Thomas and Kriegel, Hans-Peter and Schneider, Ralf and Seeger, Bernhard},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191880},
        url = {https://dl.acm.org/doi/10.1145/191839.191880},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043805923
206	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024986675
279	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022308048
488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017457851
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
1,813	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	9.5801503e-05
2,016	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.1771614e-05
2,319	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD	8.6460188e-05
2,749	Hardware Acceleration in Commercial Databases: A Case Study of Spatial Operations	2004	VLDB	8.0607411e-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
3,347	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.3933163e-05
5,905	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.9509027e-05
6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7523628e-05
8,225	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.3742569e-05
8,804	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2732683e-05
8,960	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.249844e-05
9,123	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.2254194e-05
13,234	Algorithms for Querying by Spatial Structure	1998	VLDB	4.9793485e-05
14,624	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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
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
364	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019976696
8,960	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.249844e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,758	Approximation Techniques for Spatial Data	2004	SIGMOD
2	2,588	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
3	2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD
4	4,837	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
5	6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
6	2,319	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD
7	4,927	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
8	7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
9	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
10	11,489	Optimal (Multiway) Spatial Joins	2024	PODS