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: h339fa1542b59f53e
Venue: SIGMOD
Year: 2013
Pagerank: 6.340462e-05
Overall Rank: 4,956 | 66.68%
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,219	Spatial Partitioning Techniques in SpatialHadoop	2015	VLDB	6.7262869e-05
4,568	Overlap Interval Partition Join	2014	SIGMOD	6.5300934e-05
6,939	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.6391078e-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
10,048	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	5.0899328e-05
10,061	Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs	2024	SIGMOD	5.0875952e-05
12,523	Data-driven Neuroscience: Enabling Breakthroughs Via Innovative Data Management	2013	SIGMOD	4.9793485e-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.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
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,922	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3751198e-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,120	Size Separation Spatial Join	1997	SIGMOD	7.6300049e-05
3,669	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.1125618e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
2	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
3	7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
4	1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
5	6,287	On Spatially Partitioned Temporal Join	1994	VLDB
6	2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD
7	527	Multi-Step Processing of Spatial Joins	1994	SIGMOD
8	4,837	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
9	4,927	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
10	994	Spatial Hash-Joins	1996	SIGMOD