Adaptive Sampling for Geometric Problems over Data Streams

Summary: Adaptive, single-pass sampling scheme that maintains at most 2r+1 points to approximate the convex hull of a 2D point stream, enabling many extremal geometric queries over streams. Provable guarantee: hull error O(D/r^2) (D=diameter), yielding optimal bounds and O(log r) or O(r) query time for diameter, hull-distance, separability, etc. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1327
Venue: PODS
Year: 2004
Pagerank: 5.4323688e-05
Overall Rank: 8,404 | 42.35%
DOI: 10.1145/1055558.1055595

Incoming Non-self Citations Over Time

Authors

1. John Hershberger (Mentor Graphics Corporation)
2. Subhash Suri (University of California Santa Barbara)

BibTeX Citation

@inproceedings{hershberger_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Adaptive Sampling for Geometric Problems over Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055595},
        doi = {10.1145/1055558.1055595},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hershberger, John and Suri, Subhash},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD	6.3238562e-05
7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.629255e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
1,719	The SDSS SkyServer - Public Access to the Sloan Digital Sky Survey Data	2002	SIGMOD	9.9268286e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,178	Optimal Sampling From Distributed Streams	2010	PODS
2	2,689	The Spatial Skyline Queries	2006	VLDB
3	9,676	Analysis and Application of Adaptive Sampling	2000	PODS
4	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
5	12,155	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB
6	2,443	Independent Range Sampling	2014	PODS
7	12,034	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
8	12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD
9	4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
10	7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB