Raster Intervals: An Approximation Technique for Polygon Intersection Joins

Summary: Raster intervals approximate polygons on a grid; intersecting cells form bitstring-encoded intervals. An effective filter on these approximations reduces refinement cost, delivering up to 10x end-to-end speedup and 3x improvement over prior filters. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6601
Venue: SIGMOD
Year: 2023
Pagerank: 5.4953977e-05
Overall Rank: 8,061 | 44.70%
DOI: 10.1145/3588716

Incoming Non-self Citations Over Time

Authors

1. Thanasis Georgiadis (University of Ioannina)
2. Nikos Mamoulis (University of Ioannina)

BibTeX Citation

@inproceedings{georgiadis_sigmod23,
        title = {{Raster Intervals: An Approximation Technique for Polygon Intersection Joins}},
        author = {Georgiadis, Thanasis and Mamoulis, Nikos},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588716},
        url = {https://dl.acm.org/doi/10.1145/3588716},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
10,244	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	5.093636e-05
10,776	Relevance Queries for Interval Data	2025	SIGMOD	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
11,334	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,067	Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce	2013	VLDB	0.00012327784
1,175	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011812263
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
2,732	How Good Are Modern Spatial Analytics Systems?	2018	VLDB	8.1934602e-05
3,170	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	7.6703896e-05
4,844	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.4826356e-05
5,709	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	6.1142154e-05
5,857	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	6.0644613e-05
8,614	The Case for Distance-Bounded Spatial Approximations	2021	CIDR	5.4012875e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
2	3,041	Spatio-Textual Similarity Joins	2013	VLDB
3	8,614	The Case for Distance-Bounded Spatial Approximations	2021	CIDR
4	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
5	5,709	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB
6	3,703	Approximation Techniques for Spatial Data	2004	SIGMOD
7	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
8	2,283	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD
9	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
10	3,170	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB