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: h4dd98ba60b0881d5
Venue: SIGMOD
Year: 2004
Pagerank: 7.0437238e-05
Overall Rank: 3,758 | 74.74%
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
3,927	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9192361e-05
4,211	Efficient Selection of Geospatial Data on Maps for Interactive and Visualized Exploration	2018	SIGMOD	6.7322425e-05
4,865	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.3763323e-05
6,865	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.6603286e-05
7,561	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.4958573e-05
9,910	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.1103839e-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.00076195956
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995
1,405	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001076417
2,162	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.935022e-05
3,347	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.3933163e-05
6,052	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.9028248e-05

Semantically Similar Papers

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