TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning

Summary: TOUCH enables an in-memory spatial join via hierarchical data-oriented partitioning to minimize memory footprint and comparisons. Beats in-memory and disk-based baselines, with ~10x fewer comparisons and ~100x speedups, and better density scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4695
Venue: SIGMOD
Year: 2013
Pagerank: 6.4826356e-05
Overall Rank: 4,844 | 66.77%
DOI: 10.1145/2463676.2463700

Incoming Non-self Citations Over Time

Authors

1. Sadegh Nobari (EPFL; National University of Singapore)
2. Panagiotis Karras (Rutgers University)
3. Farhan Tauheed (EPFL)
4. Stéphane Bressan (National University of Singapore)
5. Thomas Heinis (EPFL)
6. Anastasia Ailamaki (EPFL)

BibTeX Citation

@inproceedings{nobari_sigmod13,
        title = {{TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning}},
        author = {Nobari, Sadegh and Karras, Panagiotis and Tauheed, Farhan and Bressan, Stéphane and Heinis, Thomas and Ailamaki, Anastasia},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2463700},
        url = {https://dl.acm.org/doi/10.1145/2463676.2463700},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,148	Spatial Partitioning Techniques in SpatialHadoop	2015	VLDB	6.872045e-05
4,482	Overlap Interval Partition Join	2014	SIGMOD	6.6753072e-05
7,002	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.7280021e-05
8,061	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.4953977e-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
9,871	Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs	2024	SIGMOD	5.2043672e-05
9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	5.2006273e-05
12,232	Data-driven Neuroscience: Enabling Breakthroughs Via Innovative Data Management	2013	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
2,249	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.8700017e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
3,010	The Montage Extensible DataBlade Architecture	1994	SIGMOD	7.8538236e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.2750277e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
2	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
3	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
4	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
5	6,172	On Spatially Partitioned Temporal Join	1994	VLDB
6	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
7	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
8	4,740	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
9	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	994	Spatial Hash-Joins	1996	SIGMOD