Approximation Techniques for Spatial Data

Summary: Introduces approximate selectivity estimation for spatial joins and range queries in SDBMS, addressing a gap in spatial query optimization. Single-scan, incremental-update methods support inserts/deletes (streaming data) and provide provable probabilistic guarantees, with empirical evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3622
Venue: SIGMOD
Year: 2004
Pagerank: 7.1829776e-05
Overall Rank: 3,703 | 74.60%
DOI: 10.1145/1007568.1007646

Incoming Non-self Citations Over Time

Authors

1. Abhinandan Das (Cornell University)
2. Johannes Gehrke (Cornell University)
3. Mirek Riedewald (Cornell University)

BibTeX Citation

@inproceedings{das_sigmod04,
        title = {{Approximation Techniques for Spatial Data}},
        author = {Das, Abhinandan and Gehrke, Johannes and Riedewald, Mirek},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007646},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007646},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,126	Efficient Selection of Geospatial Data on Maps for Interactive and Visualized Exploration	2018	SIGMOD	6.8860475e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05
4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.5226838e-05
6,727	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.7902041e-05
7,433	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.6197531e-05
11,059	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00077458002
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
1,373	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001098638
2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.127762e-05
3,290	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.5531472e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
2	9,626	Spatial Query Optimization With Learning	2024	VLDB
3	7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB
4	6,777	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB
5	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
6	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
7	4,174	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD
8	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
9	8,614	The Case for Distance-Bounded Spatial Approximations	2021	CIDR
10	2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD