An Experimental Analysis of Iterated Spatial Joins in Main Memory

Summary: Broad benchmark of ten in-memory algorithms for iterated distance joins with batched movement updates. Surprisingly, rebuilding joins—especially synchronous R-tree traversal—usually beats incrementally maintained moving-object indexes, favoring simpler specialized strategies. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10862
Venue: VLDB
Year: 2013
Pagerank: 6.5283833e-05
Overall Rank: 4,740 | 67.49%
DOI: 10.14778/2733004.2733017

Incoming Non-self Citations Over Time

Authors

1. Benjamin Sowell (Amiato, Inc.)
2. Marcos Vaz Salles (University of Copenhagen)
3. Tuan Cao (Google)
4. Alan Demers (Cornell University)
5. Johannes Gehrke (Cornell University)

BibTeX Citation

@article{sowell_vldb13,
        title = {{An Experimental Analysis of Iterated Spatial Joins in Main Memory}},
        author = {Sowell, Benjamin and Salles, Marcos Vaz and Cao, Tuan and Demers, Alan and Gehrke, Johannes},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1882--1893},
        doi = {10.14778/2733004.2733017},
        url = {https://doi.org/10.14778/2733004.2733017},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,480	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.67565e-05
6,669	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB	5.8077717e-05
8,057	Architecting a Query Compiler for Spatial Workloads	2020	SIGMOD	5.4982831e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
9,544	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2528121e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 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
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
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
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
1,201	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00011674339
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
1,978	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.3627341e-05
2,205	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9591376e-05
2,254	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.8603695e-05
4,047	Behavioral Simulations in MapReduce	2010	VLDB	6.9380465e-05
5,740	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	6.1035012e-05
7,877	Scaling Games to Epic Proportions	2007	SIGMOD	5.5248563e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	994	Spatial Hash-Joins	1996	SIGMOD
2	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
3	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
4	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
5	9,324	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
6	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
7	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
8	2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
9	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
10	6,669	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB