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.0178846e-05
Overall Rank: 3,765 | 74.77%
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,931	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.900756e-05
4,229	Efficient Selection of Geospatial Data on Maps for Interactive and Visualized Exploration	2018	SIGMOD	6.7068084e-05
4,888	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.3522397e-05
6,890	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.6389416e-05
7,581	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.4753678e-05
9,952	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.0910746e-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.00076079812
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
432	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018400309
745	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014267268
844	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013498392
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013374869
1,412	A Model for the Prediction of R-tree Performance	1996	PODS	0.00010725178
2,176	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.9031141e-05
3,354	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.3666926e-05
6,068	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.8805774e-05

Semantically Similar Papers

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