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: 6540
Venue: SIGMOD
Year: 2023
Pagerank: 4.5421134e-05
Overall Rank: 8,260 | 42.60%
DOI: 10.1145/3588716

Incoming Non-self Citations Over Time

Authors

1. Thanasis Georgiadis
2. Nikos Mamoulis

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,510	Relevance Queries for Interval Data	2025	SIGMOD	4.1905499e-05
10,516	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	4.1905499e-05
10,984	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1905499e-05
10,991	Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs	2024	SIGMOD	4.1905499e-05
11,131	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.1905499e-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
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00014524981
1,199	Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce	2013	VLDB	0.00013358019
1,301	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00012702767
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,194	How Good Are Modern Spatial Analytics Systems?	2018	VLDB	9.3268219e-05
2,708	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	8.2643522e-05
4,778	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	5.9259497e-05
5,526	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	5.4585713e-05
6,055	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.2297716e-05
8,628	The Case for Distance-Bounded Spatial Approximations	2021	CIDR	4.4770207e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,350	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.2576191e-05
8,628	The Case for Distance-Bounded Spatial Approximations	2021	CIDR	4.4770207e-05
3,294	Spatio-Textual Similarity Joins	2013	VLDB	7.2590482e-05
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05
5,526	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	5.4585713e-05
3,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05
2,283	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD	9.1138663e-05
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
2,708	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	8.2643522e-05